Editorial for Arcadia Computing Contest 2 P5 - lp0 is on fire! - Olympiads Online Judge

Editorial for Arcadia Computing Contest 2 P5 - lp0 is on fire!

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: htoshiro

Subtask 1

For each node $i$ ~i~, we can perform a Dijkstra starting from $i$ ~i~, simulating if the source of the fire is $i$ ~i~. If the minimum distance from $i$ ~i~ to any of the non-extinguished nodes is $\leq T$ ~\leq T~, then the fire will reach a node which cannot be extinguished, making that node not a possible source. Otherwise, it is possible.

Time Complexity: $O(V(V+E)\log V)$ ~O(V(V+E)\log V)~

Subtask 2

We expand from our previous logic by understanding that if the minimum distance from a node to any of the non-extinguished nodes is $\leq T$ ~\leq T~, then that node cannot be a possible source. Thus, we can perform a multisource dijkstra with the sources being all the unextinguished nodes. All possible sources of the fire must have a minimum distance $> T$ ~> T~.

Time Complexity: $O((V+E)\log V)$ ~O((V+E)\log V)~

Comments

There are no comments at the moment.