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:
