레이팅 미적용베시는 농부들을 피해 도망치려 한다. 농부들은 \(N\) (\(2 \le N \le 5 \cdot 10^5\))개의 농장을 소유하고 있으며, \(i\)번째 농장에서 \(a_i\)번째 농장으로 가는 일방통행 도로가 있다 (\(1 \le i \le N\), \(a_i \neq i\)). 농부는 \(F\) (\(1 \le F \le N\))명 있으며, \(i\)번째 농부는 처음에 농장 \(s_i\)에 주둔해 있다 (\(1 \le s_i \le N\), 모든 \(s_i\)는 서로 다르다). 매 시간 단계마다, 모든 농부는 현재 농장의 도로를 따라 다음 농장으로 이동한다. 베시가 어느 순간이라도 어떤 농부와 같은 농장에 있게 되면 베시는 붙잡힌다.
베시가 어떤 농장 \(b\)에서 시작한다고 하자. 매 시간 단계마다 베시에게는 두 가지 선택지가 있다. 휴식을 취하거나 (현재 농장에 머무르거나), 도로를 따라 다음 농장으로 이동할 수 있다. 이동을 선택하면 농부들과 동시에 이동한다. 베시는 유한한 시간 단계 안에 어떤 농부에게도 절대 붙잡히지 않도록 움직인다.
각 시작 농장 \(b\) (\(1 \le b \le N\))에 대해, 베시가 농장 \(b\)에서 시작할 때 휴식 선택지를 고를 수 있는 최대 횟수를 구하라.
Problem credits: Alex Liang
SCORING
- 입력 2: \(N \le 50\)
- 입력 3-10: \(N \le 2000\)
- 입력 11-20: 추가 제약 없음.
Problem credits: Alex Liang
첫째 줄에 농장의 수 \(N\)과 농부의 수 \(F\)가 주어진다.
둘째 줄에 각 농장에서 나가는 일방통행 도로인 \(a_1 \ldots a_N\)이 주어진다.
셋째 줄에 각 농부의 시작 위치인 \(s_1 \ldots s_F\)가 주어진다.
\(N\)개의 줄을 출력하며, \(b\)번째 줄에는 베시가 농장 \(b\)에서 시작할 때 휴식 선택지를 고를 수 있는 최대 횟수를 나타내는 정수 하나를 출력한다. 베시가 유한한 시간 단계 후에도 절대 붙잡히지 않도록 보장할 방법이 없으면 \(-1\)을 출력한다. 베시가 무한히 많이 휴식할 수 있으면 \(-2\)를 출력한다.
4 1
2 1 4 3
1-1
0
-2
-2- Farm 1: If Bessie starts at a farm with a farmer, then she is caught immediately, and you should output \(-1\).
- Farm 2: Bessie must choose to move at every timestep to avoid being caught by the farmer who starts at farm \(1\).
- Farms 3-4: Bessie can rest an infinite number of times without being caught.
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Second Contest > Gold