/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
表示言語
/ /Score : 100 points
Problem Statement
Zye is writing AI inference code to run on REGULUS using Mobilint's SDK. Since Zye is a developer who is not very good at coding, the code he writes can compute only tree-shaped graphs.
Using this code, Zye wants to compute a rooted tree-shaped computation graph consisting of N tensors. The root of the tree is node 1. Node i of the tree represents a tensor of size w_i MiB.
A tensor represented by a leaf node is called an input tensor, and a tensor represented by a non-leaf node is called a result tensor. Input tensors already exist in memory in the initial state. The memory usage in the initial state is at most M MiB.
To compute the result tensor represented by node i, all tensors represented by the children of i must currently exist in memory. When computing the result tensor represented by node i, first the result tensor of size w_i MiB is allocated in memory. After the computation is finished, all tensors represented by the children of i are removed from memory.
The memory usage at a certain moment is defined as the sum of the sizes of all tensors that exist in memory at that moment.
Zye wants to choose the computation order so that the peak memory usage while computing the tensor represented by the root node is minimized. The peak memory usage is the maximum memory usage over the initial state and all moments during the computation.
The memory limit of the computer is M MiB. During the computation, the memory usage must always be at most M MiB.
Find the minimum peak memory usage needed to compute the result tensor represented by the root node.
Constraints
- 2 \leq N \leq 5\,000
- M = 8\,192
- w_i = 1
- 1 \leq p_i \leq N
- The given graph is a rooted tree with root node 1.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M w_1 w_2 \dots w_N p_2 p_3 \dots p_N
Here, p_i denotes the parent of node i.
Output
If it is possible to compute the result tensor represented by the root node so that the peak memory usage is at most M MiB, output the minimum possible peak memory usage.
Otherwise, output OOM instead.
Sample Input 1
8 8192 1 1 1 1 1 1 1 1 1 1 2 2 4 3 3
Sample Output 1
5
In the initial state, the tensors that exist in memory are the input tensors represented by leaf nodes 5,6,7,8. Therefore, the memory usage is 1+1+1+1=4 MiB.
For example, the result tensors can be computed in the following order.
- Compute the result tensor represented by node 4. The maximum memory usage during this step is 4+1=5 MiB.
- Compute the result tensor represented by node 3. The maximum memory usage during this step is 4+1=5 MiB.
- Compute the result tensor represented by node 2. The maximum memory usage during this step is 3+1=4 MiB.
- Compute the result tensor represented by node 1. The maximum memory usage during this step is 2+1=3 MiB.
The peak memory usage for this computation order is 5 MiB. It is impossible to make the peak memory usage at most 4 MiB, so the answer is 5.
表示言語
/ /Score : 100 points
문제
자이는 모빌린트의 SDK를 사용하여 REGULUS에서 실행할 AI 추론 코드를 작성하려고 한다. 자이는 코딩을 잘 하지 못하는 개발자이기 때문에 자이가 작성한 코드로는 트리 모양의 그래프만 계산할 수 있다.
자이는 이 코드로 텐서 N개로 이루어진 루트가 있는 트리 모양의 계산 그래프를 계산하려고 한다. 트리의 루트는 1번 노드이다. 트리의 i번 노드는 크기가 w_i MiB인 텐서를 가리킨다.
리프 노드가 가리키는 텐서를 입력 텐서, 리프가 아닌 노드가 가리키는 텐서를 결과 텐서라고 하자. 입력 텐서는 초기 상태에서 이미 메모리에 존재한다. 초기 상태의 메모리 사용량은 M MiB 이하이다.
i번 노드가 가리키는 결과 텐서를 계산하려면 i의 모든 자식 노드가 가리키는 텐서가 현재 메모리에 있어야 한다. i번 노드가 가리키는 결과 텐서를 계산할 때는 먼저 크기가 w_i MiB인 결과 텐서를 메모리에 할당하고, 계산이 끝나면 i의 모든 자식 노드가 가리키는 텐서를 메모리에서 제거한다.
어떤 시점의 메모리 사용량은 그 시점에 메모리에 존재하는 모든 텐서 크기의 합이다.
자이는 계산 순서를 적절히 조정해 루트 노드가 가리키는 텐서를 계산할 때의 피크 메모리 사용량을 최소화하려고 한다. 피크 메모리 사용량은 초기 상태와 모든 계산 과정에서의 메모리 사용량의 최댓값이다.
사용할 컴퓨터의 메모리 한도는 M MiB이다. 계산 과정에서 메모리 사용량은 항상 M MiB 이하여야 한다.
루트 노드가 가리키는 결과 텐서를 계산하는 데 필요한 피크 메모리 사용량의 최솟값을 구해 보자.
제한
- 2 \leq N \leq 5\,000
- M = 8\,192
- w_i = 1
- 1 \leq p_i \leq N
- 주어지는 그래프는 루트가 1번인 트리이다.
- 입력으로 주어지는 수는 모두 정수이다.
입력
입력은 다음 형식으로 표준 입력으로 주어진다.
N M w_1 w_2 \dots w_N p_2 p_3 \dots p_N
p_i는 i번 노드의 부모이다.
출력
피크 메모리 사용량이 M MiB 이하가 되도록 루트 노드가 가리키는 결과 텐서를 계산할 수 있다면 가능한 피크 메모리 사용량의 최솟값을 출력한다.
그렇지 않다면 대신 OOM을 출력한다.
입력 예 1
8 8192 1 1 1 1 1 1 1 1 1 1 2 2 4 3 3
출력 예 1
5
초기 상태에서 메모리에 존재하는 텐서는 5번, 6번, 7번, 8번 리프 노드가 가리키는 입력 텐서이다. 이때 메모리 사용량은 1+1+1+1=4 MiB이다.
예를 들어 다음 순서로 결과 텐서를 계산할 수 있다.
- 4번 노드가 가리키는 결과 텐서를 계산한다. 메모리 사용량의 최댓값은 4+1=5 MiB가 된다.
- 3번 노드가 가리키는 결과 텐서를 계산한다. 메모리 사용량의 최댓값은 4+1=5 MiB가 된다.
- 2번 노드가 가리키는 결과 텐서를 계산한다. 메모리 사용량의 최댓값은 3+1=4 MiB가 된다.
- 1번 노드가 가리키는 결과 텐서를 계산한다. 메모리 사용량의 최댓값은 2+1=3 MiB가 된다.
이 순서에서 피크 메모리 사용량은 5 MiB이다. 피크 메모리 사용량을 4 MiB 이하로 만드는 것은 불가능하므로 정답은 5이다.
表示言語
/ /配点 : 100 点
問題文
ザイは Mobilint の SDK を用いて，REGULUS 上で実行する AI 推論コードを書こうとしています．ザイはコーディングがあまり得意でない開発者なので，ザイが書いたコードでは木状のグラフしか計算できません．
ザイはこのコードで，N 個のテンソルからなる根付き木状の計算グラフを計算します．木の根は頂点 1 です．木の頂点 i は，サイズが w_i MiB であるテンソルを表します．
葉が表すテンソルを入力テンソル，葉でない頂点が表すテンソルを結果テンソルと呼びます．入力テンソルは初期状態ですでにメモリ上に存在します．初期状態でのメモリ使用量は M MiB 以下です．
頂点 i が表す結果テンソルを計算するためには，i のすべての子が表すテンソルが現在メモリ上に存在している必要があります．頂点 i が表す結果テンソルを計算するときは，まずサイズ w_i MiB の結果テンソルをメモリ上に確保します．その計算が完了した直後に，i のすべての子が表すテンソルをメモリから削除します．
ある時点でのメモリ使用量を，その時点でメモリ上に存在するすべてのテンソルのサイズの総和と定義します．
ザイは計算順序を適切に選ぶことで，根が表すテンソルを計算するときのピークメモリ使用量を最小化したいです．ピークメモリ使用量とは，初期状態および計算過程のすべての時点におけるメモリ使用量の最大値です．
使用するコンピュータのメモリ上限は M MiB です．計算中のどの時点においても，メモリ使用量は M MiB 以下でなければなりません．
根が表す結果テンソルを計算するために必要なピークメモリ使用量の最小値を求めてください．
制約
- 2 \leq N \leq 5\,000
- M = 8\,192
- w_i = 1
- 1 \leq p_i \leq N
- 与えられるグラフは頂点 1 を根とする根付き木である．
- 入力される数値はすべて整数
入力
入力は以下の形式で標準入力から与えられる．
N M w_1 w_2 \dots w_N p_2 p_3 \dots p_N
ここで，p_i は頂点 i の親を表す．
出力
ピークメモリ使用量が M MiB 以下となるように根が表す結果テンソルを計算できるならば，可能なピークメモリ使用量の最小値を出力する．
そうでなければ，代わりに OOM を出力する．
入力例 1
8 8192 1 1 1 1 1 1 1 1 1 1 2 2 4 3 3
出力例 1
5
初期状態では，葉である頂点 5,6,7,8 が表す入力テンソルがメモリ上に存在します．したがって，このときのメモリ使用量は 1+1+1+1=4 MiB です．
例えば，次の順序で結果テンソルを計算できます．
- 頂点 4 が表す結果テンソルを計算する．このステップ中のメモリ使用量の最大値は 4+1=5 MiB である．
- 頂点 3 が表す結果テンソルを計算する．このステップ中のメモリ使用量の最大値は 4+1=5 MiB である．
- 頂点 2 が表す結果テンソルを計算する．このステップ中のメモリ使用量の最大値は 3+1=4 MiB である．
- 頂点 1 が表す結果テンソルを計算する．このステップ中のメモリ使用量の最大値は 2+1=3 MiB である．
この計算順序におけるピークメモリ使用量は 5 MiB です．ピークメモリ使用量を 4 MiB 以下にすることはできないため，答えは 5 です．