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 to C and from b to C for each query. Then, to get the answer to the queries, we can just sum the distance from a to C and b to C.

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

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

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

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

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

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


Comments

There are no comments at the moment.