Wesley's Anger Contest 5 Problem 4 - Prison Escape

View as PDF

Submit solution


Points: 17 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types

After rigging the squirrel nation's election and obtaining full control over the nation, Wesley has ordered the imprisonment of his enemy Besley.

In order to regain his authority and power, Besley needs to escape from prison. Little does Wesley know, Besley has an accomplice (you) that has access to the prison's surveillance system, who will help Besley safely escape the prison without running into any guards.

The prison has N rooms labelled from 1 to N, with N1 two-way passageways connecting pairs of rooms, with the ith passageway connecting room xi and yi. It is possible to travel between any pair of rooms using a series of passageways, and it can be shown that the shortest path between any two rooms is unique. Security is very tight, with guards patrolling a series of rooms connected with corridors. Running into any guard will result in severe punishment, which is why planning the escape will be a necessity.

Besley will ask you Q questions in the form of two pairs of integers (ai,bi) and (ci,di), which asks that whether or not, and the earliest time he will encounter a guard if he is travelling from room ai to room bi and the guard moves from room ci to room di. Both Besley and the guard use the shortest path between the two rooms, and will only meet if they are both in the same room at the same time and neither of them have reached their destination room yet. They both leave their initial room at time=0 and take 1 second to move to an adjacent room.

Time is running out for Besley, can you quickly answer all his questions?

For this problem, Python users are recommended to use PyPy over CPython.

Constraints

For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.

For all subtasks:

2N200000
1Q200000
1xi,yiN for all 1iN1
1ai,bi,ci,diN for all 1iQ
aibi for all 1iQ
cidi for all 1iQ
Only input where it is possible to travel between any pair of rooms using a series of passageways is allowed.

Subtask 1 [4%]

2N2000
1Q2000

Subtask 2 [9%]

xi=i for all 1iN1
yi=i+1 for all 1iN1

Subtask 3 [18%]

ai=1 for all 1iQ
bi=N for all 1iQ
di=N for all 1iQ

Subtask 4 [18%]

ai=1 for all 1iQ
bi=N for all 1iQ

Subtask 5 [16%]

bi=N for all 1iQ
di=N for all 1iQ

Subtask 6 [35%]

No additional constraints.

Input Specification

The first line of input contains 2 integers, N and Q, representing the number of rooms in the prison, and the number of questions that Besley asks.

The next N1 lines describe the passageways. Each line contains 2 integers, xi and yi, indicating a two-way passageway between rooms xi and yi. Only input where it is possible to travel between any pair of rooms using a series of passageways is allowed.

The next Q lines describe the questions that Besley asks. Each line contains 4 integers, ai, bi, ci, and di, indicating that Besley is asking whether or not, and the earliest time he will encounter a guard if he is travelling from room ai to room bi and the guard moves from room ci to room di.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output Q lines. The ith line should contain the answer to the ith question. If Besley will encounter a guard if he is travelling from room ai to room bi and the guard moves from room ci to room di, output a single integer equal to the earliest time that he will encounter the guard. Otherwise, output -1.

Sample Input 1

Copy
5 4
5 3
5 1
5 2
5 4
2 4 3 1
2 5 4 1
3 1 4 5
1 5 2 5

Sample Output 1

Copy
1
-1
-1
-1

Sample Explanation 1

For the first question, Besley will encounter the guard at time=1 in room 5.
For the second, third, and fourth questions, Besley will not encounter the guard before at least one of them reaches their destination.

Sample Input 2

Copy
4 3
1 2
2 3
3 4
1 3 2 4
2 3 3 2
1 4 3 1

Sample Output 2

Copy
-1
-1
1

Sample Input 3

Copy
6 2
5 4
4 3
2 3
3 6
1 2
1 6 4 6
1 6 5 6

Sample Output 3

Copy
-1
2

Sample Input 4

Copy
7 2
6 4
1 6
7 4
4 3
2 5
4 5
1 7 1 3
1 7 2 7

Sample Output 4

Copy
0
2

Sample Input 5

Copy
5 2
5 1
1 4
2 3
2 1
2 5 4 5
4 5 3 5

Sample Output 5

Copy
1
-1

Comments


  • 1
    tappbros  commented on May 31, 2021, 11:29 p.m.

    Wonder what squirrel prisons look like. Also wonder what their surveillance system is.