레이팅 미적용정점 \(N\)개와 간선 \(M\)개로 이루어진 방향 그래프(\(2 \leq N \leq 10^5\), \(1 \leq M \leq 2 \cdot 10^5\))가 주어질 때, 농부 존의 소들은 두 명이서 다음과 같은 게임을 즐긴다.
그래프의 서로 다른 두 정점에 토큰을 하나씩 놓는다. 매 턴마다 한 플레이어인 두뇌(brain)가 나가는 간선을 따라 이동시켜야 할 토큰 하나를 고른다. 다른 플레이어인 발굽(hoof)은 그 토큰을 어느 간선을 따라 이동시킬지 고른다. 두 토큰은 절대 같은 정점에 있을 수 없다. 어느 시점에 발굽이 유효한 이동을 할 수 없게 되면 두뇌가 이긴다. 게임이 무한히 계속되면 발굽이 이긴다.
두 토큰의 시작 정점을 나타내는 \(Q\)개의 쿼리(\(1 \leq Q \leq 10^5\))가 주어진다. 각 쿼리에 대해 어느 플레이어가 이기는지 출력한다.
출제: Danny Mittal
배점
- 테스트 케이스 2-3은 \(N\le 100\), \(M\le 200\)을 만족한다.
- 테스트 케이스 4-9는 \(N\le 5000\)을 만족한다.
- 테스트 케이스 10-21은 추가 제약이 없다.
출제: Danny Mittal
첫째 줄에 \(N\)과 \(M\)이 주어진다.
다음 \(M\)개의 줄에는 각각 두 정수 \(a\)와 \(b\)가 주어지며, 이는 \(a\)에서 \(b\)로 가는 간선을 나타낸다.
그래프에는 자기 자신으로 가는 간선(self-loop)이나 다중 간선이 없다.
다음 줄에 \(Q\)가 주어진다.
마지막 \(Q\)개의 줄에는 각각 \(1\le x,y\le N\)과 \(x\neq y\)를 만족하는 두 정수 \(x\)와 \(y\)가 주어지며, 이는 토큰들의 시작 정점을 나타낸다.
길이 \(Q\)의 문자열을 출력한다. 각 문자는 두뇌가 이기면 B, 발굽이 이기면 H이다.
*참고: 이 문제의 시간 제한은 기본값의 두 배인 4초이다.*
9 10
1 2
2 3
3 4
4 7
3 5
1 6
6 8
8 9
9 6
7 2
4
1 5
1 2
1 6
2 4BHHBThe brain can win the first game by selecting node 5; then the hoof has no valid
move.
The brain can win the last game by selecting node 4 and then node 7; then the
hoof has no valid move.
The hoof wins the other games.
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > US Open > Platinum