| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 1024 MB | 41 | 12 | 10 | 40.000% |
경기과학고등학교의 지하 기지에는 수억 원 가치의 보석이 숨겨져 있다. 이 사실을 알게 된 엘투는 경기과학고등학교 지하 기지를 몰래 침입하여 보석을 훔치려고 한다. 하지만, 엘투는 곧 지하 기지가 매우 복잡한 구조로 이루어져 있다는 사실을 알게 된다. 지하 기지는 방과 방 사이가 몇몇 통로로 연결된 그래프 모양을 하고 있다. 방의 개수는 $N$개이고, 통로의 개수는 $M$개이다. 그리고, 철저한 보안을 위해 각각의 통로는 도어락으로 단단히 잠겨져 있다. 통로 중에는 같은 방으로 다시 돌아오는 것도 존재할 수 있다.
지하 기지에 대해 구체적으로 조사한 결과는 다음과 같다. 도어락을 열기 위한 도구로서 총 $K$가지의 각기 다른 카드 키가 있다. 각각의 카드 키를 분간하기 위해, 카드 키에는 타입이라고 하는 $K$ 이하의 양의 정수가 부여되어 있다. 이때, $i$번째 통로의 도어락에는 두 정수 $L_i,ドル $R_i$가 배정되어 있다. (단, 1ドル \leq i \leq M,ドル 1ドル \leq L_i \leq R_i \leq K$) 이는 만약 엘투가 타입 $L_i,ドル 타입 $L_i + 1,ドル $\cdots,ドル 타입 $R_i$의 카드 키 중 하나라도 소지하고 있다면, $i$번째 통로의 도어락을 열 수 있음을 의미한다. 카드 키는 영구적으로 사용할 수 있다.
엘투는 지하 기지의 외형에 대한 정보는 전부 구해 놓았지만, 아직 보석의 정확한 위치를 모르고 있다. 심지어, 아직 엘투 수중에는 $K$ 종류의 카드 키조차 없다. 따라서, 이 대작전을 시행하기에 앞서, 엘투는 $Q$번의 시뮬레이션을 통해 각각의 상황마다 작전의 성공 여부를 판단하고자 했다.
$j$번째 시뮬레이션은 다음과 같이 진행된다. (단, 1ドル \leq j \leq Q$) 각각의 시뮬레이션은 네 개의 정수 $X_j,ドル $Y_j,ドル $U_j,ドル $V_j$로 이루어진다. (단, 1ドル \leq X_j \leq N,ドル 1ドル \leq Y_j \leq N,ドル 1ドル \leq U_j \leq V_j \leq K$) 이는 엘투가 $X_j$번째 방에서 시작하여, 보석이 있는 위치, 곧 $Y_j$번째 방에 도달하고자 함을 의미한다. 이때, $j$번째 시뮬레이션은 엘투가 타입 $U_j,ドル 타입 $U_j + 1,ドル $\cdots,ドル 타입 $V_j$의 카드 키를 모두 소지하고 있을 때 보석이 있는 방에 도달하는 경로가 있는지를 판단해야 한다.
엘투는 동료인 당신에게 이 시뮬레이션 구현을 대신 맡겼다. 이 대작전의 성공을 위하여, 시뮬레이션을 구현해 보자.
첫 번째 줄에 $N, M, K$가 공백으로 구분되어 주어진다. 각각 방의 개수, 통로의 개수, 카드 키의 총 종류를 의미한다.
두 번째 줄부터 $M$개의 줄 중 $i$번째 줄에 $A_i,ドル $B_i,ドル $L_i,ドル $R_i$가 공백으로 구분되어 주어진다. 이는 $i$번째 통로가 $A_i$번째 방과 $B_i$번째 방을 잇고 있음을 의미한다. 또, $L_i$와 $R_i$는 $i$번째 통로의 도어락을 열 수 있는 카드 키의 타입에 대한 정보를 담고 있다.
그 다음 줄에는 $Q$가 주어진다.
그 다음 줄부터 $Q$개의 줄 중 $i$번째 줄에는 시뮬레이션의 내용 $X_i,ドル $Y_i,ドル $U_i,ドル $V_i$가 공백으로 구분되어 주어진다.
첫 번째 줄부터 $Q$개의 줄 중 $j$번째 줄에 $j$번째 시뮬레이션에 대한 답변을 출력한다.
만약, $j$번째 시뮬레이션에서 엘투가 보석에 도달할 수 있다고 판단된다면 1ドル$을 출력한다.
그렇지 않다면 0ドル$을 출력한다.
3 3 3 1 2 1 2 2 3 2 3 3 3 1 3 4 1 2 2 3 1 2 3 3 1 3 1 2 2 3 1 1
1 0 1 0
5 5 10 2 5 1 5 1 4 1 8 3 2 4 7 2 1 3 7 5 2 9 10 5 2 4 6 6 2 5 6 8 4 5 7 8 2 3 1 5 4 3 3 7
1 0 0 1 1
문제 제목에 1급 한자를 넣으려고 했으나 실패했다.
School > 경기과학고등학교 > 나는코더다 반년대회 > 나는코더다 2024 반년대회 I번