Editorial for Wesley's Anger Contest 5 Problem 4 - Prison Escape - Olympiads Online Judge

Editorial for Wesley's Anger Contest 5 Problem 4 - Prison Escape

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.

Authors: Dormi, wleung_bvg

Subtask 1

We can model the prison as a graph where the vertices are the rooms and the edges are the passageways. For each query, we can perform a depth first search to get all vertices on the path from $a_i$ $a_{i}$ to $b_i$ $b_{i}$ (ignoring $b_i$ $b_{i}$ ) and all vertices on the path from $c_i$ $c_{i}$ to $d_i$ $d_{i}$ . We can then find the first index in the two paths where the vertices are the same.

Time Complexity: $\mathcal{O}(N \cdot Q)$ $O (N \cdot Q)$

Subtask 2

In this subtask, the graph is a line. We can deal with the queries by checking the midpoint of $a_i$ $a_{i}$ and $c_i$ $c_{i}$ (if it exists) and seeing if it will be reached before Besley reaches $b_i$ $b_{i}$ and the guard reaches $d_i$ $d_{i}$ and if they will meet that midpoint at the same time. It can be seen that there is no other point where they can meet.

Time Complexity: $\mathcal{O}(N + Q)$ $O (N + Q)$

Subtask 3

For each vertex, we can store the minimum distance to any vertex on the path from $1$ $1$ to $N$ $N$ , as well as the distance to vertex $N$ $N$ . We can see that the answer only exists if the distance of vertex $c_i$ $c_{i}$ from vertex $N$ $N$ is equal to the distance of vertex $1$ $1$ from vertex $N$ $N$ , and the distance from vertex $c_i$ $c_{i}$ to the path is not equal to the distance from vertex $c_i$ $c_{i}$ to vertex $N$ $N$ . If these conditions are satisfied, then the answer is equal to the distance from vertex $c_i$ $c_{i}$ to the path.

Time Complexity: $\mathcal{O}(N + Q)$ $O (N + Q)$

Subtask 4

In this subtask, Besley and the guard will meet only if the path from $c_i$ $c_{i}$ to $d_i$ $d_{i}$ intersects the path from $1$ $1$ to $N$ $N$ . If the tree is rooted at vertex $N$ $N$ , then they only intersect if the lowest common ancestor of $c_i$ $c_{i}$ and $d_i$ $d_{i}$ is on the path from $1$ $1$ to $N$ $N$ (it is possible to do this without traditional lowest common ancestor algorithms). It can be seen that when this happens, the path from $c_i$ $c_{i}$ to $d_i$ $d_{i}$ will intersect with the path from $1$ $1$ to $N$ $N$ over some path of vertices. We can then use a method similar to subtask 2 to determine if they will meet on this path, adjusting for the time the guard first reaches the path from $1$ $1$ to $N$ $N$ .

Time Complexity: $\mathcal{O}(N + Q)$ $O (N + Q)$

Subtask 5

In this subtask, we can root the tree at vertex $N$ $N$ . Besley and the guard will only meet if the depth of $a_i$ $a_{i}$ and $c_i$ $c_{i}$ are the same. They will first meet at their lowest common ancestor as long as it is not vertex $N$ $N$ . The answer is the difference between the depth of $a_i$ $a_{i}$ and the lowest common ancestor of $a_i$ $a_{i}$ and $c_i$ $c_{i}$ .

Time Complexity: $\mathcal{O}(N + Q)$ $O (N + Q)$

Subtask 6

Special thanks to 300iq for providing the idea behind this solution.

It can be proven that if a solution exists, it will always be the middle vertex $x$ $x$ on the path from $a_i$ $a_{i}$ to $c_i$ $c_{i}$ . $x$ $x$ can be found by first finding the distance between the two vertices using the lowest common ancestor ( $\text{lca}$ $lca$ ), and then selecting the middle vertex in $\mathcal{O}(\log N)$ $O (\log N)$ using any standard method (binary lifting, heavy light decomposition, etc…). The distance between two vertices $u$ $u$ and $v$ $v$ in a tree is $\text{depth}(u) + \text{depth}(v) - 2 \cdot \text{depth}(\text{lca}(u, v))$ $depth (u) + depth (v) - 2 \cdot depth (lca (u, v))$ . Here, a solution exists if and only if $x$ $x$ is on both the path from $a_i$ $a_{i}$ to $b_i$ $b_{i}$ and on the path from $c_i$ $c_{i}$ to $d_i$ $d_{i}$ and is not $b_i$ $b_{i}$ or $d_i$ $d_{i}$ . We can check if vertex $x$ $x$ is on a path from vertices $u$ $u$ to $v$ $v$ by checking if the set $\{\text{lca}(x, u), \text{lca}(x, v)\}$ ${lca (x, u), lca (x, v)}$ is the same as the set $\{\text{lca}(u, v), x\}$ ${lca (u, v), x}$ . We can query for the lowest common ancestor ( $\text{lca}$ $lca$ ) in $\mathcal{O}(1)$ $O (1)$ time with $\mathcal{O}(N)$ $O (N)$ or $\mathcal{O}(N \cdot \log N)$ $O (N \cdot \log N)$ precomputation using any data structure that supports range minimum queries over Euler tour indices.

Time Complexity: $\mathcal{O}(N + Q \cdot \log N)$ $O (N + Q \cdot \log N)$

Comments

There are no comments at the moment.