시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 256 MB | 70 | 30 | 29 | 47.541% |
효원이랑 승재는 다음과 같은 게임을 한다. 게임은 정점 $1,2,\cdots,n$ 사이를 간선으로 연결해서 만든 그래프 위에서 진행되며, 이 그래프는 임의의 두 정점 사이에 경로가 존재하고, 모든 정점은 자기 자신과 연결해주는 loop를 가졌다. 각 정점 $i$마다 돌을 $w_i>0$개 놓은 상태로 시작한다.
효원이는 정점 $s$부터 시작한다. 효원이랑 승재는 순서를 바꿔가며 다음과 같이 그래프 위에서 움직이며 돌을 제거한다.
마지막 돌을 제거하는 사람이 이긴다. 다음은 한 게임 플레이의 예시다. 아직 효원이랑 승재가 규칙을 잘 모르는 상태로 플레이를 해서 최적으로 플레이하지 않았을 수도 있다.
이제 효원이랑 승재는 이 게임의 규칙을 잘 이해한다. 두 명 모두 최적으로 게임을 할 경우, 누가 이기는지 판정하는 프로그램을 작성하시오.
첫째 줄에는 정점의 수 $n$, 간선의 수 $m$, 게임을 시작하는 정점 $s$가 주어진다. 그래프는 임의의 두 정점 사이에 경로가 존재하고, 모든 정점은 자기 자신과 연결하는 loop를 가진다. 그래프의 크기는 $1\leq n\leq 50,000$, $2n-1\leq m\leq 500,000$을 만족한다.
둘째 줄에는 각 정점에 있는 돌의 개수 $w_1,w_2,\cdots,w_n$가 공백으로 구분되어 주어진다. 모든 정점에서 돌의 수는 $1$개 이상 $2^{20}$개 미만이다.
셋째 줄부터 $(m+2)$번째 줄까지 간선에 관한 정보가 두 수 $u$와 $v$로 주어진다. 이는 $u$와 $v$ 사이에 무방향 간선이 있다는 의미이다. $u=v$일 수 있다.
효원이랑 승재 둘다 최적으로 게임을 할 경우, 이기는 사람을 출력하라. 효원이가 이기는 경우 "
", 승재가 이기는 경우 "hwy
"을 따옴표 없이 출력하라.sjh
추가 제한 조건이 없다.
1 1 1 4 1 1
hwy
2 3 1 1 1 1 1 1 2 2 2
sjh
2 3 1 1 2 1 1 1 2 2 2
sjh
2 3 1 2 1 1 1 1 2 2 2
hwy