Editorial for Escape de la prisión

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: humbertoyusta

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: $O ( N ⋅ 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: $O ( N + Q )$ ~O ( N + Q )~

Alternatively, we could have been solved this subtask with binary search.

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: $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: $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: $O ( N + Q )$ ~O ( N + Q )~

Subtask 6

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, and then selecting the middle vertex using any standard method (binary lifting, heavy light decomposition, etc...). The distance between two vertices $u$ ~u~ and $v$ ~v~ in a tree is $depth ( u ) + depth ( v ) - 2 ⋅ 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 ${ lca ( x , u ) , lca ( x , v ) }$ ~{ lca ( x , u ) , lca ( x , v ) }~ is the same as the set ${ lca ( u , v ) , x }$ ~{ lca ( u , v ) , x }~.

Time Complexity: $O ( ( N + Q ) ⋅ \log ⁡ N )$

Comments

There are no comments at the moment.