| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 10 초 | 1024 MB | 78 | 35 | 15 | 34.091% |
우주 최고의 프로그래머 교준이는 $N$명의 학생을 데리고 "최강의 PS 군단"을 만들고자 한다.
$N$명의 학생 중에는 같이 있을 때 시너지 효과가 발생하는 학생 조합이 있다. $i$번 학생의 "시너지 동료" 집합을 $A_i$라 하자. 이는, $i$번 학생은, 모든 $j \in A_i$에 대하여, 자신이 $j$번 학생과 같이 있을 때 시너지 효과가 나온다고 생각함을 의미한다. 반대로, $j \not \in A_i$라면, $i$번 학생은 자신이 $j$번 학생과 같이 있어도 시너지 효과가 나온다고 생각하지 않음을 의미한다. $(0 \le i \le N-1)$
교준이가 생각하는 "최강의 PS 군단"의 조건은 꽤 까다롭다. $N$명의 학생이 다음 조건을 모두 만족할 때, 교준이는 "이 $N$명의 학생이 최강의 PS 군단을 이룬다''고 말한다:
$N$명의 학생은 교준이에게 있어 "최강의 PS 군단"인지 판별하는 프로그램을 작성하시오.
첫 번째 줄에 세 정수 $N,ドル $B,ドル $C$가 주어진다.
두 번째 줄부터 $N$개의 줄에 걸쳐, $N$명의 학생의 "시너지 동료"에 대한 정보가 주어진다.
$(i+2)$번째 줄에는 정수 $|A_i|$와, 집합 $A_i$에 속한 $|A_i|$개의 정수가 주어진다 $(0 \le i \le N - 1)$.
만약, $N$명의 학생이 "최강의 PS 군단"을 이루지 않는다면, 첫 번째 줄에 "NO"(따옴표 제외)를 출력한다.
만일, $N$명의 학생이 "최강의 PS 군단"을 이룬다면, 첫 번째 줄에 "YES"(따옴표 제외)를 출력한다. 여기서, $K$개의 집합 $P_1, P_2, \cdots, P_K$가 다음 조건을 모두 만족한다고 하자:
계속하여, 두 번째 줄에는 정수 $K$를 출력한다.
또한, 세 번째 줄부터 $K$개의 줄에 걸쳐, $K$개의 집합 $P_1, P_2, \cdots, P_K$애 대한 정보를 출력한다. $(i+2)$번째 줄에는 정수 $| P_i |$와, 집합 $P_i$에 속한 $| P_i |$개의 정수를 오름차순으로 차례대로 출력한다 $(1 \le i \le K)$.
위와 같은 조건을 만족하는 $(K, P_1, P_2, \cdots, P_K)$가 여러 가지라면, 그 중 아무거나 하나를 취해도 정답으로 인정된다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 20 | $N \le 16$ |
| 2 | 37 | $N \le 250,ドル $C \le 2$ |
| 3 | 12 | $C \le 2$ |
| 4 | 31 | 추가 제약 조건 없음 |
1 0 1 0
NO
1 1 0 0
YES 1 1 0
2 1 1 1 1 1 0
YES 2 1 1 1 0
4 2 2 3 1 2 3 1 0 2 0 3 2 2 0
YES 2 2 0 1 2 2 3
Olympiad > Baltic Olympiad in Informatics > BOI 2017 E번