34256번 - 레몬 왕국의 용사, 비타로 서브태스크언어 제한함수 구현

문제

용감한 용사 비타로는 던전 퀘스트에 도전한다.

던전은 0,1,ドル\dots,N-1$번까지 번호가 붙은 $N$개의 방으로 이루어져 있다. 0ドル$번 방을 제외한 각 방은 정확히 하나의 상위 방을 가진다. $i$번 방($i \ge 1$)의 상위 방은 $P[i]$번 방이며, 반대로 $i$번 방은 $P[i]$번 방의 하위 방이다. 한 방은 여러 개의 하위 방을 가질 수 있으며, 0ドル$번 방은 상위 방을 가지지 않는다.

비타로는 다음 규칙에 따라 방을 탐사한다.

• 처음에는 반드시 0ドル$번 방을 탐사한다.
• 이후에는 아직 탐사하지 않은 방 중에서, 그 상위 방이 이미 탐사된 방을 하나 골라 탐사한다.

던진의 $i$번 방은 난이도 $R[i]$와 레벨 $L[i]$를 가진다. 각 방의 레벨 $L[i]$는 변하지 않는다. 난이도 $R[i]$는 $i$번 방에서 출발하여 하위 방 방향으로 0ドル$번 이상 이동해 도달할 수 있는 방들 중, 이미 탐사한 방의 개수로 정의된다. 따라서 아직 탐사하지 않은 방의 난이도는 0ドル$이고, 0ドル$번 방의 난이도는 항상 지금까지 탐사한 방의 개수이다.

새로운 방을 탐사할 때마다 던전에 있는 모든 방에 다음 규칙이 적용된다. 이에 따라 일부 방에 몬스터가 추가될 수 있다. 이미 탐사한 방에서 몬스터가 추가될 수 있음에 유의하라.

• $L[i] \le R[i]$이면, $i$번 방에는 $L[i] + (L[i] + 1) + \cdots + R[i]$ 마리의 몬스터가 새로 추가된다.
• $L[i] > R[i]$이면, $i$번 방에는 몬스터가 추가되지 않는다.
• 난이도가 0ドル$인 방(아직 탐사하지 않은 방)에는 몬스터가 추가되지 않는다.

비타로는 싸움을 최소화하고 싶기 때문에, 새로운 방을 탐사할 때는 탐사 직후 던전 전체에 새로 추가되는 몬스터 수가 최소가 되는 방을 선택한다. 만약 그런 방이 여러 개라면, 번호가 가장 작은 방을 선택한다.

하지만 비타로는 $P[i]$는 알지만 $L[i]$는 모른다. 이를 위해 그는 탐사할 수 있는 방 중 하나를 선택하여 조사하고, 그 방의 레벨 $L[i]$를 알 수 있다.

비타로가 던전 퀘스트를 성공적으로 마칠 수 있게 도와주자.

함수 구현

함수 구현에 앞서 #include "brave.h" 를 통해 "brave.h" 헤더 파일을 포함해야 한다.

당신은 다음 함수를 구현해야 한다.

void bitaroTravel(int N, std::vector<int> P)

• $N$: 방의 수
• $P$: 각 방의 상위 방을 나타내는 길이 $N$의 배열 $(P[0] = 0$으로 정의된다$)$
• 이 함수는 하나의 테스트 케이스에 대해 단 한 번만 호출된다.

이 함수 안에서 아래의 두 함수를 호출해 비타로의 탐험을 시뮬레이션해야 한다.

int explore(int i)

• $i$: 새롭게 탐사할 방의 번호 (0ドル \le i \le N - 1$)
• 첫 번째 호출에서는 반드시 0ドル$번 방을 탐사해야 한다.
• 이후 호출에서는 $i$번 방이 아직 탐사되지 않았고, $P[i]$번 방이 이미 탐사된 상태여야 한다.
• 조건에 맞지 않으면 $-1$을 반환한다. (탐사 규칙 위반 여부와는 별개이다.)
• 그 외의 경우 1ドル$을 반환한다.

int investigate(int i)

• $i$: 조사할 방 번호 (0ドル \le i \le N - 1$)
• 이때 $i$번 방은 탐사되지 않았고, $P[i]$번 방은 탐사된 상태여야 한다.
• 모든 방은 단 한 번만 조사할 수 있다. 즉, 같은 방을 여러 번 조사할 수 없다.
• 조건을 만족하지 않으면 $-1$을 반환한다.
• 그 외의 경우 $L[i]$을 반환한다.

explore 함수를 총 $N$번 호출해 모든 방을 탐험한 뒤에는 bitaroTravel 함수를 종료해야 한다.

종료 후, 방을 탐사한 순서가 문제의 조건에 맞으면 맞았습니다!! 판정을, 그렇지 않으면 틀렸습니다 판정을 받는다.

제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.

입력

출력

제한

• 2ドル \leq N \leq 300\ 000$.
• 1ドル \leq L[i] \leq 10$ (0ドル \le i \le N - 1$).
• $P[0]=0$.
• 0ドル \le P[i] < i$ (1ドル \le i \le N - 1$).

서브태스크

힌트

예제

다음과 같은 호출을 생각하자.

bitaroTravel(6, [0, 0, 0, 2, 3, 1])

다음은 가능한 함수 호출 순서 중 하나이다.

investigate(5) 호출 직후, 탐사할 수 있는 후보는 3ドル$번과 5ドル$번 방이다.

• 3ドル$번을 탐사하면, 던전 전체에 새로 추가되는 몬스터 수는 $(1 + 2 + 3) + (1) + (1) = 12$마리.
• 5ドル$번을 탐사하면, 던전 전체에 새로 추가되는 몬스터 수는 $(1 + 2 + 3 + 4) + (1 + 2) + (1) = 14$마리.

따라서 추가 몬스터 수가 더 적은 3ドル$번 방을 탐사해야 한다.

최종적으로 올바른 탐사 순서는 $[0, 2, 1, 3, 4, 5]$ 이다.

샘플 그레이더

Sample grader의 입력 형식은 아래와 같다.

$N$

$P[1] \ P[2] \ \cdots \ P[N-1]$

$L[0] \ L[1] \ \cdots \ L[N-1]$

비타로가 $i$번째로 탐사한 방을 $K[i]$라고 하자. Sample grader는 다음을 출력한다.

$U[1] \ U[2] \ \cdots \ U[N]$

Sample grader는 실제 채점에서 사용하는 그레이더와 다를 수 있음에 유의하라.

첨부

• brave.zip