DAG 위의 게임
플래티넘 IV의견: 0
정점 \(N\)개, 간선 \(M\)개의 방향 비순환 그래프(DAG)가 주어진다. 그래프 위에 \(T\)개의 토큰이 놓여 있다(한 정점에 여러 토큰이 있을 수 있다). 한 번의 차례에 토큰 하나를 골라, 그 토큰이 있는 정점에서 나가는 간선을 따라 인접한 다음 정점으로 옮긴다. 어떤 토큰도 더 이상 움직일 수 없게 된(모든 토큰이 진출 간선이 없는 정점에 있는) 사람이 진다.
선공이 이기면 선공, 후공이 이기면 후공을 출력하라.
\(1 \le N \le 100{,}000\)
\(0 \le M \le 200{,}000\) (DAG, 모든 간선 \(u < v\))
\(1 \le T \le 100{,}000\), 토큰 위치 \(1 \le p \le N\)
첫 줄에 \(N\), \(M\).
이후 \(M\)줄에 방향 간선 \(u\ v\) (DAG, \(u
다음 줄에 토큰 수 \(T\).
마지막 줄에 토큰들의 위치 \(T\)개.
선공 또는 후공을 출력한다.
4 3
1 2
2 3
3 4
1
1
선공경로 1→2→3→4. 토큰 1개가 정점1에 있음. 정점1의 그런디는 경로 길이 패리티로 \(g(4)=0,g(3)=1,g(2)=0,g(1)=1\ne0\) → 선공.
3 2
1 2
1 3
2
1 1
후공1→2, 1→3. 토큰 2개 모두 정점1. \(g(1)=1\), XOR \(=1\oplus1=0\) → 후공.
riseoj 작성
출처 Original
평가 및 의견
DAG 위의 게임
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
DAG 위의 게임