| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 235 | 44 | 37 | 18.049% |
디미고에서 공부가 너무나도 하기 싫었던 ecode는 야자 시간에 의미 없는 그래프를 그렸다. 어떻게든 자신이 만든 그래프에 의미를 부여하고 싶었던 ecode는 아래와 같은 규칙을 덧붙였다.
이러한 규칙에 따라 작성한 결과 아래와 같은 그래프를 얻었다.
옆에서 이를 지켜보던 ecode의 짝꿍인 oh051525는 이를 한심하게 쳐다보며 말하였다.
차라리 이 그래프로 게임까지 만들어버리지 그래?
광기가 서린 ecode는 그녀의 아이디어에 감탄하며 이 그래프로 게임을 만들어버렸다!!
ecode가 만든 게임은 출발 지점에서 시작해 그래프의 간선을 따라 이동하는 게임이다. 게임의 한 턴은 다음과 같이 진행된다.
ecode는 친구들과의 대결에서 승리하기 위해, $T$번째 턴에 마지막으로 도착한 노드의 번호를 미리 알아내려고 한다. 게임의 답을 최대한 빨리 알고 싶은 ecode를 위해 이를 해결하는 코드를 작성해 보자!
첫 번째 줄에 노드의 개수 $N$과 간선의 개수 $K,ドル 작업의 실행 횟수 $T$가 주어진다. $(1\leq N\leq 10^5;$ 0ドル\leq K\leq 3\times 10^5;$ 1ドル\leq T\leq 5\times 10^5)$
두 번째 줄부터 $K$개의 줄에 걸쳐, 간선으로 연결된 두 노드의 번호 $x$와 $y$가 공백으로 구분되어 주어진다.
$K+2$번째 줄에 각 노드의 등급을 나타내는 $N$개의 정수 $A_1, A_2, ..., A_N$가 공백으로 구분되어 주어진다. $A_i$는 $i$번 노드의 등급을 의미한다. $(1\leq A_i\leq 5\times 10^5)$ 1ドル$등급 노드는 항상 한 개 존재한다.
$K+3$번째 줄에 $i$번 노드의 화살표가 가리키는 하위 등급 노드의 번호가 공백으로 구분되어 주어진다. $i$번 노드에 연결된 하위 등급 노드가 없다면 $-1$이 입력된다.
게임의 규칙을 어기는 경우는 입력으로 주어지지 않는다.
$T$번째 턴에 마지막으로 도착한 노드의 번호를 출력한다.
15 19 2 1 2 2 3 3 9 10 4 2 10 4 2 11 9 11 8 12 11 4 11 10 12 1 5 5 15 5 12 6 5 6 1 7 6 14 13 7 13 1 2 3 4 3 2 3 6 4 3 5 6 5 6 4 2 4 9 11 12 5 13 -1 11 4 12 -1 14 -1 -1
12
첫 번째 턴이 끝난 후 그래프의 상태는 다음과 같다.
두 번째 턴이 끝난 후 그래프의 상태는 다음과 같다.
최종적으로 도착한 노드의 번호가 12ドル$이므로 정답은 12ドル$이다.
10 11 5 3 2 4 7 8 10 5 3 1 2 8 5 5 7 3 4 4 6 3 1 7 9 1 2 3 4 5 8 8 7 12 11 2 3 5 6 8 -1 9 10 -1 -1
10
School > 한국디지털미디어고등학교 > 제 1회 2024 디미고 프로그래밍 챌린지 H번