| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 2048 MB | 8 | 8 | 8 | 100.000% |
$0$번부터 $N-1$번까지 번호가 매겨진 $N$개의 정점으로 이루어진 루트 있는 트리가 주어진다. $0$번 정점이 이 트리의 루트이며, 모든 정점은 자식의 개수가 $0$개 혹은 $2$개이다. 자식이 $2$개인 정점은 왼쪽, 오른쪽 자식이 정해져 있다. 트리의 각 간선 $e$는 양의 정수 길이 $c_e$를 가진다.
우리는 이 트리를 2차원 좌표 평면 위에 그릴 것이다. 각 정점 $v$는 서로 다른 정수 격자점 $m_v = (x_v, y_v)$에 그린다. 이때 루트 정점은 $m_0 = (0, 0)$에 그려야 한다. 정수 격자점은 $x$좌표와 $y$좌표가 모두 정수인 점을 뜻한다.
$v$와 $v$의 부모 $p$를 잇는 간선 $e = (p, v)$는 좌표 평면 상에서 $m_p$와 $m_v$를 잇는 경로로 그려진다. 이 경로는 다음 조건을 모두 만족해야 한다:
트리 그리기에서 정점 $v$의 깊이를 $L(v) = x_v + y_v$로 정의하자. 우리가 그리게 될 트리에서 자식이 $0$개인 정점은 모두 같은 깊이를 가져야 한다. 이 깊이를 격자 깊이라고 하자.
모든 올바른 트리 그리기에 대해서 격자 깊이가 최소가 되는 경우를 구하여라.
다음 함수를 구현해야 한다.
long long compute_min_depth(int N, vector<int> P, vector <int> C, vector<int> D)
제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.
트리에서의 두 정점 사이의 거리를 두 정점을 잇는 유일한 경로를 구성하는 간선들의 길이 합이라 정의하자.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $N \le 7$ |
| 2 | 8 | 자식이 $2$개인 모든 정점 $v$에 대해 $v$의 자식 중 하나는 자식이 $0$개이다. |
| 3 | 21 | $N \le 5000$, 자식이 $0$개인 모든 정점 $v$에 대해 $0$번 정점과 $v$의 거리는 $K$ ($\le 2500$)로 동일하다. |
| 4 | 29 | $N \le 5000$, 모든 정점 $v$에 대해 $0$번 정점과 $v$의 거리는 $2500$ 이하이다. |
| 5 | 32 | 추가적인 제약조건이 없다. |
서브태스크 3은 격자 깊이가 정확히 $K$인 트리 그리기가 존재하지 않으면 compute_min_depth가 $-1$을 반환해도 정답으로 인정한다. 보다 정확하게는:
서브태스크 3에서는 자식이 $0$개인 모든 정점 $v$에 대해 $0$번 정점과 $v$의 거리가 동일하며, 그 거리가 $K$임을 유념하자.
예제 1
다음 호출을 생각해보자:
compute_min_depth(5, [4, 0, 4, 0], [1, 2, 1, 1], [0, 1, 1, 0])
격자 깊이가 $2$ 미만이 되도록 하는 트리 그리기가 존재하지 않음을 증명할 수 있다.
따라서 함수는 $2$를 반환해야 한다.
예제 2
다음 호출을 생각해보자:
compute_min_depth(9, [0, 0, 1, 1, 2, 2, 5, 5], [2, 1, 1, 1, 1, 1, 1, 1], [0, 1, 0, 1, 0, 1, 0, 1])
따라서 함수는 $4$를 반환해야 한다.
샘플 그레이더의 입력 형식은 다음과 같다.
샘플 그레이더는 다음 형식으로 답을 출력한다:
compute_min_depth의 반환값Olympiad > 국제정보올림피아드 대표학생 선발고사 > 2026 > 1차 선발고사 3번
C++17, C++20, C++23, C++26, C++17 (Clang), C++20 (Clang)