Editorial for GlobeX Cup '18 J5 - Errands - DMOJ: Modern Online Judge

Editorial for GlobeX Cup '18 J5 - Errands

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: Plasmatic

For the first subtask, it suffices to BFS from $a$ ~a~ to $C$ ~C~ and from $b$ ~b~ to $C$ ~C~ for each query. Then, to get the answer to the queries, we can just sum the distance from $a$ ~a~ to $C$ ~C~ and $b$ ~b~ to $C$ ~C~.

For this subtask, if $C$ ~C~ is unreachable through either the first or second BFS, print This is a scam!.

Time Complexity: $\mathcal O(Q(N+M))$ ~\mathcal O(Q(N+M))~

For the second subtask, note that we can instead BFS from $C$ ~C~ to $a$ ~a~ and $b$ ~b~ instead of the other way around. With that information in mind, we can also note that $C$ ~C~ stays constant throughout the queries, so we only need to run one BFS at the beginning from $C$ ~C~ to every other node.

Now, all we have to do for each query is sum $dist[a]$ ~dist[a]~ and $dist[b]$ ~dist[b]~.

Note that if either $a$ ~a~ or $b$ ~b~ are unreachable, print This is a scam!.

Time Complexity: $\mathcal O(N+M+Q)$ ~\mathcal O(N+M+Q)~

Comments

There are no comments at the moment.