루미 알고리즘

#1137플래티넘게임게임

KOI 2026 2차코딩초등부 4번, 중등부 3번출제 박영우이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

게임

원제: 게임

문제

앨리스와 밥은 NN개의 방과 이 방들을 연결하는 통로들로 이루어진 미로에서 게임을 하려고 한다.

미로의 방에는 1,2,⋯ ,N1, 2, \cdots, N의 번호가 붙어 있다. 미로의 어떤 방들은 출구를 가지고 있는데, ii (1≤i≤N)(1 \le i \le N)번 방에는 Ai=1A_i = 1이면 출구가 있고, Ai=0A_i = 0이면 없다.

미로를 연결하는 통로는 정확히 MM쌍의 방 중 하나의 쌍을 연결한다. 같은 쌍의 방을 잇는 통로가 여러 개 존재할 수 있다.

구체적으로는, 각 ii (1≤i≤M)(1 \le i \le M)에 대하여, aia_i번 방과 bib_i번 방을 잇는 서로 다른 통로가 cic_i개 존재한다.

임의의 두 방 사이를 통로들을 통해 오갈 수 있음이 보장되지 않음에 유의하라.

앨리스와 밥은 총 QQ번의 게임을 하려고 하는데, jj (1≤j≤Q)(1 \le j \le Q)번째 게임은 다음과 같이 진행된다.

  • 앨리스가 미로의 sjs_j번 방으로 들어간다.
  • 앨리스는 다음 규칙에 따라 인접한 방으로 이동할 수 있다.
    • 앨리스가 현재 xx번 방에 있다 하자. 앨리스는 xx번 방과 연결된 kjk_j개의 서로 다른 통로를 고른다. 이때 같은 방을 연결하는 여러 통로를 동시에 고를 수 있다. 만약 xx번 방과 연결된 통로의 수가 kjk_j보다 작아 서로 다른 kjk_j개의 통로를 고르는 것이 불가능할 경우, 이동할 수 없다.
    • 앨리스가 선택을 마친 후 밥은 앨리스가 고른 kjk_j개의 통로 중 하나를 고른다.
    • 앨리스는 밥이 고른 통로가 잇는 반대쪽 방으로 이동한다.
  • 앨리스가 위 규칙에 따라 다른 방으로 이동하는 것을 00번 이상 반복하여 출구가 있는 방에 도달하면 승리한다.

sjs_j번 방에 출구가 있는 경우, 게임이 시작할 때 앨리스가 있는 방에 출구가 있으므로 앨리스가 승리할 수 있음에 유의하라.

앨리스는 자신이 승리하기 위해서 최선을 다하며, 밥 역시 앨리스가 승리하지 못하게 하기 위해 최선을 다한다. 즉, 게임 중 밥이 어떤 선택을 하더라도 앨리스가 매 순간 적절한 선택을 하여 항상 출구가 있는 방에 도달할 수 있다면 앨리스가 승리하고, 그렇지 않으면 승리할 수 없다.

각 게임에 대해, 앨리스가 게임에서 승리할 수 있을지 아닐지를 판정하라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤N≤200 0001 \le N \le 200\,000
  • 0≤M≤400 0000 \le M \le 400\,000
  • 1≤Q≤200 0001 \le Q \le 200\,000
  • 정수 ii (1≤i≤N)(1 \le i \le N)에 대하여, AiA_i는 00 또는 11이다.
  • 정수 ii (1≤i≤M)(1 \le i \le M)에 대하여 1≤ai<bi≤N1 \le a_i < b_i \le N
  • 서로 다른 두 정수 ii, jj (1≤i,j≤M)(1 \le i, j \le M)에 대하여, ai≠aja_i \ne a_j 또는 bi≠bjb_i \ne b_j이다.
  • 정수 ii (1≤i≤M)(1 \le i \le M)에 대하여 1≤ci≤1 000 000 0001 \le c_i \le 1\,000\,000\,000
  • 정수 jj (1≤j≤Q)(1 \le j \le Q)에 대하여 1≤sj≤N1 \le s_j \le N
  • 정수 jj (1≤j≤Q)(1 \le j \le Q)에 대하여 1≤kj≤1 000 000 000 000 000 0001 \le k_j \le 1\,000\,000\,000\,000\,000\,000

부분문제

  1. (6점) M=N−1M = N - 1; 정수 ii (1≤i≤M)(1 \le i \le M)에 대하여, ai=ia_i = i와 bi=i+1b_i = i + 1을 만족한다. 출구는 11번 방에만 존재한다. 즉, A1=1A_1 = 1과 A2=A3=⋯=AN=0A_2 = A_3 = \cdots = A_N = 0을 만족한다.
  2. (8점) M=N−1M = N - 1; 정수 ii (1≤i≤M)(1 \le i \le M)에 대하여, ai=1a_i = 1과 bi=i+1b_i = i + 1을 만족한다.
  3. (7점) k1=k2=⋯=kQ=1k_1 = k_2 = \cdots = k_Q = 1
  4. (14점) k1=k2=⋯=kQk_1 = k_2 = \cdots = k_Q
  5. (15점) s1=s2=⋯=sQs_1 = s_2 = \cdots = s_Q
  6. (16점) N≤3 000N \le 3\,000; M≤3 000M \le 3\,000; 정수 jj (1≤j≤Q)(1 \le j \le Q)에 대하여 kj≤3 000k_j \le 3\,000
  7. (34점) 추가 제약 조건 없음.

입력 형식

첫 줄에 미로의 방의 수를 나타내는 정수 NN, 통로 종류의 수를 나타내는 정수 MM, 앨리스와 밥이 진행할 게임의 수를 나타내는 정수 QQ가 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 NN개의 정수 A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N이 공백으로 구분되어 차례대로 주어진다.

그다음 MM개의 줄에 걸쳐, 통로에 대한 정보가 주어진다. 이 중 ii (1≤i≤M)(1 \le i \le M)번째 줄에는 세 정수 aia_i, bib_i, cic_i가 공백으로 구분되어 차례대로 주어진다. 이는 미로에 aia_i번 방과 bib_i번 방을 연결하는 cic_i개의 통로가 있음을 의미한다.

그다음 QQ개의 줄에 걸쳐, 앨리스와 밥이 진행할 QQ번의 게임에 대한 정보가 주어진다. 이 중 jj (1≤j≤Q)(1 \le j \le Q)번째 줄에는 두 정수 sjs_j와 kjk_j가 공백으로 구분되어 차례대로 주어진다.

출력 형식

첫 줄부터 QQ개의 줄에 걸쳐, 답을 출력한다. 이 중 jj (1≤j≤Q)(1 \le j \le Q)번째 줄에는 jj번째 게임에 대하여 앨리스가 승리할 수 있다면 YES, 그렇지 않다면 NO를 출력해야 한다.

예제

예제 1

입력
5 5 5
0 0 1 0 0
1 2 1
1 3 1
1 4 2
2 3 2
3 4 1
2 1
1 2
3 3
4 4
5 1
출력
YES
YES
YES
NO
NO

이 예제에서 미로에는 총 55개의 방과 77개의 통로가 있고, 출구는 33번 방에만 있다. 앨리스와 밥은 총 55번의 게임을 진행한다.

첫 번째 게임에서 앨리스는 처음에 22번 방에 있고, 이동 시 11개의 통로를 골라야 한다. 앨리스가 처음에 33번 방으로 향하는 통로를 하나 고르면 밥도 같은 통로를 고르게 되고, 출구가 있는 33번 방으로 이동하여 게임에서 승리할 수 있다.

두 번째 게임에서 앨리스는 처음에 11번 방에 있고, 이동 시 22개의 통로를 골라야 한다. 이때 앨리스는 다음과 같은 전략으로 게임에서 승리할 수 있다.

  • 처음에 22번, 33번 방으로 향하는 통로를 하나씩 선택한다.
    • 밥이 33번 방으로 향하는 통로를 선택할 경우,

    33번 방에는 출구가 있으므로 앨리스가 승리한다.

    • 밥이 22번 방으로 향하는 통로를 선택했다 하자. 이때 앨리스가 33번 방으로 향하는 통로를 22개 고르면 밥은 두 통로 중 하나를 선택해야 하고, 앨리스가 33번 방으로 이동하여 게임에서 승리한다.

따라서 앨리스는 밥의 선택과 무관하게 출구가 있는 33번 방으로 이동하게 되어 게임에서 승리할 수 있다.

세 번째 게임에서 앨리스는 처음에 33번 방에 있고, 이동 시 33개의 통로를 골라야 한다. 33번 방에는 출구가 있으므로, 앨리스는 아무 이동을 하지 않아도 승리한다.

네 번째 게임에서 앨리스는 처음에 44번 방에 있고, 이동 시 44개의 통로를 골라야 한다. 그러나 44번 방과 연결된 통로는 11번 방으로 향하는 것 22개, 33번 방으로 향하는 것 11개로 총 33개이다. 따라서 앨리스는 다른 방으로 이동할 수 없고, 게임에서 승리할 수 없다.

다섯 번째 게임에서 앨리스는 처음에 55번 방에 있고, 이동 시 11개의 통로를 골라야 한다. 55번 방에는 출구가 없는데, 어떠한 통로도 연결되어 있지 않으므로 다른 방으로 이동할 수 없다. 따라서 앨리스는 게임에서 승리할 수 없다.

예제 2

입력
4 3 4
1 0 0 0
1 2 2
2 3 3
3 4 1
1 3
2 2
3 3
4 1
출력
YES
YES
NO
YES

세 번째 게임에서 앨리스는 33번 방에서 시작하고, 이동 시 33개의 통로를 골라야 한다. 이때 밥이 다음과 같은 전략을 사용할 경우 앨리스는 승리할 수 없다.

  • 앨리스가 처음에 44번 방으로 향하는 통로를 하나라도 골랐다면, 밥은 그 통로를 선택한다. 그러면 앨리스는 44번 방으로 이동하게 되는데, 44번 방과 연결된 통로는 하나이므로 앨리스는 더 이상 이동할 수 없고, 게임에서 승리할 수 없다.
  • 만약 앨리스가 44번 방으로 향하는 통로를 고르지 않았을 경우, 가능한 상황은 22번 방으로 향하는 통로를 세 개 고른 것이다. 이 경우 밥은 22번 방으로 향하는 통로를 고르고, 앨리스는 22번 방으로 이동한다.
  • 22번 방에서 연결되어 있는 통로 중 11번 방으로 향하는 것은 22개이므로, 앨리스는 이동을 위해 반드시 33번 방으로 향하는 통로를 골라야 한다. 이때 밥도 33번 방으로 향하는 통로를 선택하면 앨리스는 다시 33번 방으로 이동하게 된다.

위 전략은 앨리스가 44번 방으로 들어가기 전까지 계속하여 사용할 수 있다. 따라서 앨리스가 이동을 아무리 반복해도 출구가 있는 유일한 방인 11번 방에 도달할 수 없고, 게임에서 승리할 수 없다.

예제 3

입력
4 3 3
0 1 1 0
1 2 1
1 3 3
1 4 2
4 2
1 3
4 3
출력
YES
YES
NO

예제 4

입력
2 0 2
1 0
1 1
2 1
출력
YES
NO

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2026년 2차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.