Skrivača
레이팅 미적용의견: 0
Marin and Luka are playing a popular kids game called Hide and Seek (Skrivača).
They are playing in their house which has \(n\) rooms, and \(m\) pairs of rooms are
connected by a door. Rooms are labeled from 1 to \(n\) and for each pair of rooms
there exists a path from one room to another.
Luka has thought of a hiding strategy: when Marin enters room \(v\), Luka will hide
in room \(a@@RISE_MATH_BLOCK_0@@v\)0. In each step of the game, firstly Marin chooses a room \(u\)
adjecent to his current room and enters it. After that, Luka knows Marin is in room \(u\) so by his hiding
strategy he hides in room \(a@@RISE_MATH_BLOCK_1@@u\) and that in one
step of the game he can pass through an arbitrary number of rooms.
Marin will find Luka when both of them are located in the same room, at that momement the game ends.
Marin found out about Luka’s hiding strategy so he wants you to determine for each starting room if
Marin can find Luka in a finite amount of steps, and if he can, determine the least amount of steps
necessary if both of them play optimally. (Marin plays such that he finds Luka in the least amount of
steps and Luka plays such that Marin finds him in the most amount of steps).
Subtask 1 (15 points): \(n \le 1\,000\), \(m \le 2\,000\)
Subtask 2 (25 points): \(m = n - 1\)
Subtask 3 (30 points): Luka’s hiding strategy will be such that he will never attempt to hide in the same or adjecent room to where Marin is currently located, and the structure of the house will be such that the game can end in at most 5 different rooms independent of Luka’s hiding strategy
Subtask 4 (40 points): No additional constraints.
In the first line there are integers \(n\), \(m\) (\(1 \le n \le 2 \cdot 10^{5}\), \(n - 1 \le m \le mi\)n(\(5 \cdot 10^{5}\), {n}{(}{−}
2
), the number of
rooms and the number of pairs of connected rooms.
In the second line there are \(n\) integers \(a@@RISE_MATH_BLOCK_0@@i \le n\)), describing Luka’s hiding strategy.
In \(i-th\) of the next \(m\) lines there are integers \(x@@RISE_MATH_BLOCK_1@@i\) (\(1 \le x@@RISE_MATH_BLOCK_2@@i\)̸ = \(y@@RISE_MATH_BLOCK_3@@i\) and
room \(y\)\(i\) are connected. Between each pair of rooms there will be at most one connection.
In the first and only line print \(n\) numbers, where the \(i-th\) number represents the least amount of steps
necessary for Marin to find Luka if Marin starts in room \(i\), \(or -1\) if Marin can’t find Luka.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 15점 | \(n \le 1\,000\), \(m \le 2\,000\) |
2 | 25점 | \(m = n - 1\) |
3 | 30점 | Luka’s hiding strategy will be such that he will never attempt to hide in the same or adjecent room to where Marin is currently located, and the structure of the house will be such that the game can end in at most 5 different rooms independent of Luka’s hiding strategy |
4 | 40점 | No additional constraints. |
4 4
3 4 1 2
1 2
2 3
3 4
4 1-1 -1 -1 -18 9
2 3 2 1 6 5 6 7
1 2
1 3
2 4
3 4
4 5
4 6
6 7
5 7
4 81 2 2 2 1 1 1 19 8
1 9 1 1 1 9 9 9 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 90 1 1 2 1 1 2 1 1Clarification of the second example:
Marin enters room 8 from room 4 in the first step, and in the secend he goes back to room 4. Luka needs
to pass through room 4 to get from room 7 to room 1 so Marin can find Luka in 2 steps.
평가 및 의견
Skrivača
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Skrivača