루미 알고리즘

#1136플래티넘간식 분배간식 분배

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

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

간식 분배

원제: 간식 분배

문제

NN명의 학생과 NN개의 간식이 있다. 학생들과 간식에는 각각 1,2,⋯ ,N1, 2, \cdots, N의 번호가 붙어 있다.

각 학생은 NN개의 간식 중 하나 이상의 간식을 좋아한다. 보다 구체적으로, ii (1≤i≤N)(1 \le i \le N)번 학생은 CiC_i개의 간식을 좋아하며, 그 간식들의 번호는 Ai,1,Ai,2,⋯ ,Ai,CiA_{i,1}, A_{i,2}, \cdots, A_{i,C_i}이다.

처음에 방 안에는 NN종류의 간식이 정확히 하나씩 놓여 있다. 다음과 같은 과정을 통해 학생들에게 간식을 분배하려고 한다.

  • NN명의 학생을 적절한 순서로 한 번에 한 명씩 방에 들여보낸다.
  • 방에 들어간 학생은 현재 방에 남아있는 간식 중 자신이 좋아하는 모든 간식을 가져간다. 만약, 방 안에 자신이 좋아하는 간식이 하나도 없다면, 아무 간식도 가져가지 않는다.

NN명의 학생이 방에 들어가는 순서를 적절히 정하여, 모든 학생이 정확히 하나의 간식을 가져가도록 하는 것이 가능한지 판별하라. 만약 가능하다면, 그러한 순서를 아무거나 하나 구하라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤N≤200 0001 \le N \le 200\,000
  • 정수 ii (1≤i≤N)(1 \le i \le N)에 대하여 1≤Ci≤N1 \le C_i \le N
  • C1+C2+⋯+CN≤500 000C_1 + C_2 + \cdots + C_N \le 500\,000
  • 정수 ii (1≤i≤N)(1 \le i \le N)와 정수 jj (1≤j≤Ci)(1 \le j \le C_i)에 대하여 1≤Ai,j≤N1 \le A_{i,j} \le N
  • 정수 ii (1≤i≤N)(1 \le i \le N)에 대하여, CiC_i개의 정수 Ai,1,Ai,2,⋯ ,Ai,CiA_{i,1}, A_{i,2}, \cdots, A_{i,C_i}의 값은 모두 서로 다르다.

부분문제

  1. (6점) 정수 ii (1≤i≤N)(1 \le i \le N)에 대하여 Ci=1C_i = 1
  2. (11점) 모든 학생이 정확히 하나의 간식을 가져가도록 하는 순서가 존재한다면, 1,2,⋯ ,N1, 2, \cdots, N의 번호 순서도 그러한 조건을 만족한다.
  3. (8점) N≤5N \le 5
  4. (12점) N≤18N \le 18
  5. (18점) N≤300N \le 300
  6. (20점) N≤5 000N \le 5\,000
  7. (25점) 추가 제약 조건 없음.

입력 형식

첫 줄에 학생과 간식의 수를 나타내는 정수 NN이 주어진다.

그다음 NN개의 줄에 걸쳐, NN명의 학생이 좋아하는 간식에 대한 정보가 주어진다. 이 중 ii (1≤i≤N)(1 \le i \le N)번째 줄에는 정수 CiC_i와 그 뒤에 CiC_i개의 정수 Ai,1,Ai,2,⋯ ,Ai,CiA_{i,1}, A_{i,2}, \cdots, A_{i,C_i}가 공백으로 구분되어 차례대로 주어진다.

출력 형식

만약, 모든 학생이 정확히 하나의 간식을 가져가도록 하는 순서가 존재하지 않는다면, 첫 줄에 -1을 출력한다.

만약, P1,P2,⋯ ,PNP_1, P_2, \cdots, P_N의 번호 순서대로 학생들이 방에 들어갈 때 모든 학생이 정확히 하나의 간식을 가져간다면, 첫 줄에 NN개의 정수 P1,P2,⋯ ,PNP_1, P_2, \cdots, P_N을 공백으로 구분하여 출력한다.

가능한 출력이 여러 개라면 그중 아무거나 하나를 출력해도 정답으로 인정된다.

예제

예제 1

입력
3
2 1 2
2 2 3
1 2
출력
3 1 2

각 학생이 좋아하는 간식은 다음과 같다.

  • 11번 학생은 1,21, 2번 간식을 좋아한다.
  • 22번 학생은 2,32, 3번 간식을 좋아한다.
  • 33번 학생은 22번 간식을 좋아한다.

33번, 11번, 22번 학생이 이 순서대로 방에 들어가면 각 학생은 정확히 하나의 간식을 가져간다.

  • 처음에 방에는 1,2,31, 2, 3번 간식이 모두 하나씩 있다.
  • 33번 학생이 방에 들어가면 22번 간식을 가져간다. 이후 방에는 1,31, 3번 간식이 남아있다.
  • 11번 학생이 방에 들어가면 11번 간식을 가져간다. 이후 방에는 33번 간식이 남아있다.
  • 22번 학생이 방에 들어가면 33번 간식을 가져간다.

마찬가지로, 33번, 22번, 11번 학생이 이 순서대로 방에 들어가도 모든 학생은 정확히 하나의 간식을 가져간다.

예제 2

입력
2
2 1 2
2 1 2
출력
-1

두 학생 모두 모든 종류의 간식을 좋아하므로, 학생들이 어떤 순서로 방에 들어가더라도 처음으로 방에 들어간 학생이 모든 간식을 가져가게 된다.

예제 3

입력
4
1 3
1 2
3 4 2 3
2 1 2
출력
1 2 3 4

자료

출처 표기

출처: 한국정보올림피아드(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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.