26415번 - Ghost 서브태스크점수다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB | 44 | 23 | 19 | 52.778% |
문제
하나의 유령이 대한민국을 배회하고 있다. KOI 2022 2차 대회라는 유령이...
KOI 도시는 $N$ 개의 교차로와 $N - 1$ 개의 양방향 도로로 이루어져 있으며, 임의의 서로 다른 두 교차로를 도로만을 사용하여 오갈 수 있다. 즉, 도시의 도로망은 트리 구조를 이룬다. 도로는 2차원 평면 상에 있으며, 두 도로가 끝점을 제외한 위치에서 교차하지 않는다.
KOI 도시는 몇십년 전까지만 하여도 작은 마을이었지만, 사람이 유입되고 크기가 커지면서 급격히 팽창하기 시작하였다. 급격한 팽창 과정에서 시장은 행정 편의를 위해 교차로에 $1$ 이상 $N$ 이하의 번호를 매겼다. 이 때 번호 시스템은 다음과 같은 성질을 만족한다.
- $1$번 교차로는 도시의 중심으로, $2$개 이상의 도로와 인접함이 보장된다.
- 교차로에 매겨진 번호는 $1$번 교차로를 루트로 한 트리의 전위 순회 순서 (Preorder) 중 하나이다.
- 모든 교차로에 대해서, 인접한 (도로로 직접 연결된) 교차로 중 가장 번호가 작은 교차로를 생각해 보자. 이 교차로를 기준으로 시계 반대 방향으로 인접한 교차로의 번호를 나열했을 때, 번호는 증가한다.
KOI 도시에 많은 사람들이 유입되면서, 교통 체증 문제가 심화되었다. 시장은 이를 해결하기 위해 교통 인프라가 가장 빈약한 도시들을 외곽 순환 도로로 이었다. KOI 도시에 있는 모든 교차로 중, 단 $1$개의 도로와 인접한 교차로들의 번호를 증가하는 순서대로 나열한 리스트를 $\{v_1, v_2, \dots , v_k\}$ 라고 하자. 시장은, 모든 $1 \le i \le k$ 에 대해서, $v_i$번 교차로와 $v_{(i \pmod k)+1}$번 교차로를 잇는 양방향 도로를 건설하였다. 번호 시스템의 특성상, 두 도로가 끝점을 제외한 위치에서 교차하지 않게끔 외곽 순환 도로를 이을 수 있음을 관찰하면 좋다.
하지만, 교통 체증 문제가 심화되었다고 트리를 그래프로 만드는 것을 좋아하는 노동자들은 없다. 교통 체증 문제가 해소되면 출퇴근 시간이 줄어서, 자본가들이 노동자를 착취하기 쉬워지기만 할 뿐이다. 노동자들은 자본가들의 역겨운 수작에 넘어가지 않고, KOI 도시 트리에서 HLD와 센트로이드 분할을 할 수 있던 좋은 옛날로 돌아가고 싶다. 노동자들은 먼저 사회주의 혁명을 일으켜 자본가들을 몰아내고, 다음과 같은 새로운 트리를 만들어서, 기존 KOI 도시의 구조를 재건하고 싶다.
- 새로운 트리는 $4N$ 개 이하의 정점을 가진다. 새로운 트리의 정점이 $K$ 개라 할 때, 각 정점의 번호를 $1, 2, \ldots, K$ 라는 정수로 표현하자.
- 새로운 트리의 $i$ 번째 정점에는 집합 $X_i$ 가 존재하며, $X_i$ 는 $\{1, \ldots, N\}$ 의 부분집합이다.
- 원래 KOI 도시의 모든 도로 $(u, v)$ 에 대해, $\{u, v\}$ 를 모두 포함하는 집합 $X_i$ 가 존재한다. 모든 도로라 하면, 원래 트리를 이루던 도로와, 외곽 순환 도로를 포함한다.
- 모든 $1 \le j \le N$ 에 대해서, $j \in X_i$ 를 만족하는 정점들의 집합을 $S_j$ 라고 했을 때, $S_j$ 는 비어있지 않아야 하고, 혁명적 집합 이어야 한다.
- 모든 $i$ 에 대해서 $|X_i| \le 4$ 를 만족해야 한다. ($|X_i| \le 5$ 를 만족할 경우 부분 점수를 받을 수 있다.)
새로운 트리의 어떠한 정점 부분집합 $S$ 가 혁명적 이라는 것은 다음과 같다. $S$에 속하는 서로 다른 두 정점 $u$, $v$에 대하여, $S$에 속하는 정점만을 이용하여 새로운 트리 위에서 $u$, $v$ 사이를 오갈 수 있다면, “$u$와 $v$는 $S$ 위에서 연결되어 있다”고 하자. $S$ 가 혁명적이라는 것은, $S$ 에서 서로 다른 두 정점 $u, v$을 골랐을 때, $u, v$ 가 항상 $S$ 위에서 연결되어 있음을 뜻한다.
예를 들어, 아래와 같은 새로운 트리를 생각하자.
만일, $S = \{1, 2, 3, 4, 5, 6\}$라면, $(1, 2), (3, 5), (4, 6)$은 각각 서로 $S$ 위에서 연결되어 있다. 그러나, $(1, 6), (2, 6)$ 은 각각 서로 $S$ 위에서 연결되어 있지 않다.
노동자들을 도와, KOI 도시의 도로망이 주어졌을 때, 새로운 트리와 각 정점의 집합 $X_i$ 를 출력하라.
입력
첫 번째 줄에 KOI 도시의 교차로 수 $N$이 주어진다.
이후 $N - 1$개의 줄이 주어진다. 이 중 $i$번째 줄에는, 하나의 정수 $p_i$ 가 주어진다. 이는, 교차로 $p_i$와 교차로 $i + 1$를 잇는 양방향 도로가 존재함을 뜻한다.
입력으로 주어지는 도로들은 외곽 순환 도로가 아니다.
출력
첫 번째 줄에 새로운 트리의 정점 수 $K$ 를 출력하라. $1 \le K \le 4N$ 을 만족해야 한다.
이후 $K$ 개의 줄을 출력하라. 이 중 $i$ 번째 줄의 첫 번째 정수는, 집합 $X_i$ 의 크기이다. 이후 $X_i$ 개의 서로 다른 정수를 공백으로 구분하여 출력한다. 각 정수는 $X_i$ 에 속하는 원소들을 나타낸다.
이후 $K - 1$ 개의 줄에 걸쳐 새로운 트리의 간선을 차례대로 출력하라.
정답이 항상 존재함을 증명할 수 있다.
제한
- $4 \le N \le 100\,000$
- $1 \le p_i \le i$
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 40 | $4$개 이상의 도로와 인접한 교차로가 존재하지 않음. |
| 2 | 60 | 추가 제약 조건 없음. |
출력이 문제의 모든 조건을 만족한다면 100%의 점수를 얻는다.
출력이 $|X_i| \le 4$ 를 제외한 문제의 모든 조건을 만족하고, $|X_i| \le 5$ 를 만족한다면, 40%의 점수를 받는다.
예제 입력 1
4 1 1 1
예제 출력 1
2 4 1 2 3 4 0 1 2
노트
$X_i$ 는 공집합이어도 된다.
만약 $X_i$ 의 크기 조건이 없다면, 예제와 유사하게 $K = 1$, $X_1 = \{1, 2, \ldots, N\}$ 을 잡는 자명한 해가 존재한다.
출처
Camp > Petrozavodsk Programming Camp > Winter 2023 > Day 4: KAIST+KOI Contest, Grand Prix of Korea C번
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호