I am looking for help identifying a problem from my country's national olympiad (they steal problems from other countries olympiads and reword them), or some insight as to the solution for this problem. I've tried for a full day, but I haven't succeeded in (a) finding the source of the problem, or (b) solving the problem. They don't give post an editorial or anything, they just have an online grader.↵
↵
↵
↵
This is the problem: ↵
↵
↵
↵
~~~~~↵
Catching Crewmates↵
↵
Input file: standard input↵
↵
Output file: standard output↵
↵
Time limit: 5 seconds↵
↵
Memory limit: 512 megabytes↵
↵
↵
The Skeld is a spacecraft which can be modeled as a collection of n rooms numbered 1, 2, . . . , n and n − 1↵
doors connecting these rooms such there is a unique path between any two rooms.↵
↵
Currently, there is a single crewmate and a single impostor on the Skeld. The crewmate is initially in the↵
room x and the impostor is hiding in a vent in the room y.↵
↵
The crewmate is scared of the impostor and is thus constantly running through the doors between different↵
rooms, in an attempt to get away from the impostor. The crewmate will also mark any door with a↵
breadcrumb trail when they run through it, and then know not to pass through that door again. However,↵
if the floor gets cleaned near a marked door, then the breadcrumb trail will be lost and the crewmate will↵
be able to run through the door again.↵
↵
Additionally, right before the crewmate runs through a door, the impostor is able to clean the floor near↵
any door that has been marked by a breadcrumb trail, close any door permanently, or do nothing.↵
The impostor wants to catch the crewmate as quickly as possible and would like to know how many↵
“moves” this would take.↵
↵
Another way to describe this problem is as a two-player game, where the impostor moves first.↵
On their turn, the impostor can do any of the following:↵
↵
• Clean the floor near a door marked with a breadcrumb trail, making it possible for the crewmate↵
to pass through this door again.↵
↵
• Close any open door on the Skeld, permanently.↵
↵
• Do nothing. (This does not count as a move for the impostor)↵
↵
Note that in no case will the impostor open a door that they have closed before.↵
↵
On the crewmate’s turn, they will do the following:↵
↵
• Choose an open and unmarked door to an adjacent room, and run through it, marking the door↵
with a breadcrumb trail in the process.↵
↵
• Do nothing only if no such doors exist.↵
↵
The moment that the crewmate is forced to enter the room where the impostor is hiding, the games ends↵
and the impostor catches the crewmate.↵
↵
In this two-player game, the goal of the crewmate is to survive and maximize the number of moves it↵
takes the impostor to catch them, and the goal of the impostor is to minimize the number of moves it↵
takes to catch the crewmate.↵
↵
Assuming both the crewmate and the impostor act optimally, what is the minimum number of moves↵
(doors closed or cleaned) it will takes the impostor to catch the crewmate?↵
↵
Input↵
↵
The first line of input contains three integers n, y, x (1 ≤ y, x ≤ n ≤ 10^6) from the problem statement.↵
The next n − 1 lines of input each contain two integers a and b (1 ≤ a, b ≤ n) indicating a door↵
connecting two distinct rooms a and b.↵
↵
Output↵
↵
Output a single integer the minimum number of moves it will take the impostor to catch the crewmate,↵
assuming both act optimally.↵
↵
Scoring↵
↵
Subtask 1: (0 Points) Examples.↵
↵
Subtask 2: (20 Points) n ≤ 10.↵
↵
Subtask 3: (25 Points) It is guaranteed that there is a door between rooms x and y.↵
↵
Subtask 4: (20 Points) n ≤ 1000.↵
↵
Subtask 5: (35 Points) No further constraints.↵
↵
Example↵
↵
Input:↵
↵
10 1 4↵
↵
1 2↵
↵
2 3↵
↵
2 4↵
↵
3 9↵
↵
3 5↵
↵
4 7↵
↵
4 6↵
↵
6 8↵
↵
7 10↵
↵
↵
Answer:↵
↵
4↵
↵
Note↵
↵
One possible scenario which explains the example output:↵
↵
• Impostor closes the door between rooms 4 and 7.↵
↵
• Crewmate runs to room 6. The door between rooms 4 and 6 is now marked.↵
↵
• Impostor closes the door between rooms 6 and 8.↵
↵
• Crewmate cannot move.↵
↵
• Impostor cleans the floor near the door between rooms 4 and 6.↵
↵
• Crewmate runs to room 4. The door between rooms 4 and 6 is now marked.↵
↵
• Impostor closes the door between rooms 2 and 3.↵
↵
• Crewmate runs to room 2. The door between rooms 2 and 4 is now marked.↵
↵
• Impostor does nothing.↵
↵
• Crewmate can only run into room 1 and gets caught by the impostor.↵
~~~~~↵
↵
↵
↵
↵
↵
I would appreciate it if anybody could give an insight to the solution or a link to the original. thank you.
↵
↵
↵
This is the problem: ↵
↵
↵
↵
~~~~~↵
Catching Crewmates↵
↵
Input file: standard input↵
↵
Output file: standard output↵
↵
Time limit: 5 seconds↵
↵
Memory limit: 512 megabytes↵
↵
↵
The Skeld is a spacecraft which can be modeled as a collection of n rooms numbered 1, 2, . . . , n and n − 1↵
doors connecting these rooms such there is a unique path between any two rooms.↵
↵
Currently, there is a single crewmate and a single impostor on the Skeld. The crewmate is initially in the↵
room x and the impostor is hiding in a vent in the room y.↵
↵
The crewmate is scared of the impostor and is thus constantly running through the doors between different↵
rooms, in an attempt to get away from the impostor. The crewmate will also mark any door with a↵
breadcrumb trail when they run through it, and then know not to pass through that door again. However,↵
if the floor gets cleaned near a marked door, then the breadcrumb trail will be lost and the crewmate will↵
be able to run through the door again.↵
↵
Additionally, right before the crewmate runs through a door, the impostor is able to clean the floor near↵
any door that has been marked by a breadcrumb trail, close any door permanently, or do nothing.↵
The impostor wants to catch the crewmate as quickly as possible and would like to know how many↵
“moves” this would take.↵
↵
Another way to describe this problem is as a two-player game, where the impostor moves first.↵
On their turn, the impostor can do any of the following:↵
↵
• Clean the floor near a door marked with a breadcrumb trail, making it possible for the crewmate↵
to pass through this door again.↵
↵
• Close any open door on the Skeld, permanently.↵
↵
• Do nothing. (This does not count as a move for the impostor)↵
↵
Note that in no case will the impostor open a door that they have closed before.↵
↵
On the crewmate’s turn, they will do the following:↵
↵
• Choose an open and unmarked door to an adjacent room, and run through it, marking the door↵
with a breadcrumb trail in the process.↵
↵
• Do nothing only if no such doors exist.↵
↵
The moment that the crewmate is forced to enter the room where the impostor is hiding, the games ends↵
and the impostor catches the crewmate.↵
↵
In this two-player game, the goal of the crewmate is to survive and maximize the number of moves it↵
takes the impostor to catch them, and the goal of the impostor is to minimize the number of moves it↵
takes to catch the crewmate.↵
↵
Assuming both the crewmate and the impostor act optimally, what is the minimum number of moves↵
(doors closed or cleaned) it will takes the impostor to catch the crewmate?↵
↵
Input↵
↵
The first line of input contains three integers n, y, x (1 ≤ y, x ≤ n ≤ 10^6) from the problem statement.↵
The next n − 1 lines of input each contain two integers a and b (1 ≤ a, b ≤ n) indicating a door↵
connecting two distinct rooms a and b.↵
↵
Output↵
↵
Output a single integer the minimum number of moves it will take the impostor to catch the crewmate,↵
assuming both act optimally.↵
↵
Scoring↵
↵
Subtask 1: (0 Points) Examples.↵
↵
Subtask 2: (20 Points) n ≤ 10.↵
↵
Subtask 3: (25 Points) It is guaranteed that there is a door between rooms x and y.↵
↵
Subtask 4: (20 Points) n ≤ 1000.↵
↵
Subtask 5: (35 Points) No further constraints.↵
↵
Example↵
↵
Input:↵
↵
10 1 4↵
↵
1 2↵
↵
2 3↵
↵
2 4↵
↵
3 9↵
↵
3 5↵
↵
4 7↵
↵
4 6↵
↵
6 8↵
↵
7 10↵
↵
↵
Answer:↵
↵
4↵
↵
Note↵
↵
One possible scenario which explains the example output:↵
↵
• Impostor closes the door between rooms 4 and 7.↵
↵
• Crewmate runs to room 6. The door between rooms 4 and 6 is now marked.↵
↵
• Impostor closes the door between rooms 6 and 8.↵
↵
• Crewmate cannot move.↵
↵
• Impostor cleans the floor near the door between rooms 4 and 6.↵
↵
• Crewmate runs to room 4. The door between rooms 4 and 6 is now marked.↵
↵
• Impostor closes the door between rooms 2 and 3.↵
↵
• Crewmate runs to room 2. The door between rooms 2 and 4 is now marked.↵
↵
• Impostor does nothing.↵
↵
• Crewmate can only run into room 1 and gets caught by the impostor.↵
~~~~~↵
↵
↵
↵
↵
↵
I would appreciate it if anybody could give an insight to the solution or a link to the original. thank you.
