Editorial for COI '13 #3 Mostovi

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.

Initially, let's notice that the memory can hold only blocked roads and built bridges because their amount will be sufficiently small. A query about the existence of a road between two cities $G_1$ ~G_1~ and $G_2$ ~G_2~ can be split into three cases:

The towns are located on opposite river banks:

Let's find the first bridge which can be reached with roads from $G_1$ ~G_1~ and from which there are roads to reach $G_2$ ~G_2~. If such a bridge does not exist, then a way from $G_1$ ~G_1~ to $G_2$ ~G_2~ doesn't exist. The previous statement is true because, no matter what other bridge we pick, it will require the existence of all the roads our first bridge requires, and some additional roads.
The towns are located on the same river bank and the direction of roads on that bank is from $G_1$ ~G_1~ to $G_2$ ~G_2~:

Bridges cannot help us in this case because they will lead us in the opposite direction of town $G_2$ ~G_2~ and therefore we need to check whether there is a blocked road between $G_1$ ~G_1~ and $G_2$ ~G_2~. We can do this by finding the first blocked road which appears after town $G_1$ ~G_1~. If this road is located before town $G_2$ ~G_2~, a way does not exist, otherwise it exists.
The towns are located on the same river bank and the direction of roads on that bank is from $G_2$ ~G_2~ to $G_1$ ~G_1~:

Let's notice that we cannot reach $G_2$ ~G_2~ by only using roads. We need to find the first bridge which can be reached from $G_1$ ~G_1~ and cross to the other river bank. Now this case comes down to the first case. The choice of bridge is fine because of the similar reason as in the first case.

For answering queries about the first blocked road after a certain town, we can, for example, keep the blocked roads in a balanced search tree (STL set).

For answering queries about the first bridge that can be reached by roads from town $G$ ~G~ we simply find, in a similar way to queries about roads, the first bridge after town $G$ ~G~ and check whether there is a blocked road between them.

In the first case, we want to know about the first bridge after $G_1$ ~G_1~ and before $G_2$ ~G_2~, but it is sufficient to notice that the bridge is either first after $G_1$ ~G_1~ or first before $G_2$ ~G_2~ or they are equal.

Complexity: $\mathcal O(M \log N)$ ~\mathcal O(M \log N)~

Comments

There are no comments at the moment.