시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 61 | 4 | 4 | 28.571% |
Dumbo the elephant has a huge labyrinth with n rooms numbered 1 . . . n and n−1 passages in such way that it is possible to reach any room from any other room. Unfortunately, a mouse sneaked into the labyrinth. Dumbo is terribly afraid of mice, so he sets a mousetrap in room t. Obviously, the mouse avoids the room with the trap, so Dumbo has to think of a better strategy to bait the mouse into the trap. The mouse constantly runs around and never stops, unless it has nowhere to move. He also knows that the mouse leaves a dirty trail of droppings and footprints in every passage it uses. The mouse then refuses to use a dirty passage again. Dumbo can clean a dirty passage, or block a passage with stones. By blocking passages or cleaning them, he wants to force the mouse to run into the trap. He would like to do this in a minimal number of moves, as he feels highly uncomfortable in the presence of a mouse.
We can describe this as a game for two players. The mouse tries to maximize the number of Dumbo’s moves. The Dumbo tries to win in minimal number of moves. The first player is Dumbo. On his turn, he may clean one dirty passage of the labyrinth or block one passage. It doesn’t matter if the blocked passage is clean or not. He cannot unblock a passage. He may, however, choose to do nothing. Turns in which Dumbo decides to do nothing do not count as moves. When it is the mouse’s turn, the mouse will choose a clean unblocked passage and run to the adjacent room down that passage. If there is no such passage leading from mouse’s current room, the mouse won’t move.
Initially, all the passages are clean, the mouse is in room m, the trap is in room t, and it is Dumbo’s turn. What is the minimum number of moves (passages cleaned and blocked) Dumbo needs if both players play optimally (mouse’s goal is to maximize the number of Dumbo’s moves)?
Integers n, t and m will be given in the first line, separated by spaces. n − 1 lines follow. In each line, ai and bi are given, separated by a space, which indicates a passage between rooms ai and bi.
Note that the input size is large.
Your program should print the number of Dumbo’s moves.
번호 | 배점 | 제한 |
---|---|---|
1 | 20 | n ≤ 10 |
2 | 25 | It is guaranteed that a passage between rooms m and t exists. |
3 | 20 | n ≤ 1000 |
4 | 35 | No additional constraints |
10 1 4 1 2 2 3 2 4 3 9 3 5 4 7 4 6 6 8 7 10
4
One possible scenario:
Dumbo made 4 moves.