G - Typical Path Problem Editorial by zifanwang


In this problem, we can use an algorithm called Round-square tree. In a round-square tree, each of the original points corresponds to a round point, and each extremely large point bi-connected subgraph corresponds to a square point.

So we only need to determine whether there is a square point on the path from point \(A\) to point \(C\) in the round-square tree that is connected to point \(B\) by an edge.

It can be solved in a total of \(O(N+M)\) time.

Sample code in C++: https://atcoder.jp/contests/abc318/submissions/45198737

posted:
last update: