Help for IOI 2016 — Roller Coaster Railroad problem

Правка en1, от ricardogg, 2019-06-22 13:14:48

I tried solving this problem and I coded the first two subtasks easily. However, for the other two subtasks I tried reading the editorial. Even after reading I don't understand the solution. Here is link for the problem: https://ioinformatics.org/files/ioi2016problem2.pdf and the link of editorial https://ioinformatics.org/files/ioi2016solutions.pdf (3rd page)

I don't really get what the balance array does in the third subtask. I tried looking at every "special sections" as things that change the speed of the train from s[i] to t[i]. But I don't really get why the balance array has to be equal to all zeros and why the graph has to be connected and how in the forth subtask it is reduced to MST problem.

Thanks in advance for any help.

Теги #ioi, #help

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский ricardogg 2019-06-22 13:14:48 799 Initial revision (published)