#include <bits/stdc++.h>
using namespace std;
vector<int> adj[(int)2e5+7];
vector<int> dp[(int)2e5+7];
int N,D;
vector<int> smallMerge(vector<int> a, vector<int> b){
// for (int i=0; i<D; i++){
// cout<<a[i]<<' ';
// }
// cout<<'\n';
// for (int i=0; i<D; i++){
// cout<<b[i]<<' ';
// }
// cout<<'\n';
// int tmp;
// tmp = a[D-1];
// for (int i=D-1; i>=1; i--) a[i] = a[i-1]; a[0] = tmp+1;
// tmp = b[D-1];
// for (int i=D-1; i>=1; i--) b[i] = b[i-1]; b[0] = tmp+1;
vector<int> maxa(D+1, 0), maxb(D+1, 0);
vector<int> res(D, 0);
for (int i=D-1; i>=0; i--) maxa[i] = max(maxa[i+1], a[i]);
for (int i=D-1; i>=0; i--) maxb[i] = max(maxb[i+1], b[i]);
for (int i=0; i<D; i++){
int ni = max(i, D-i);
res[i] = max(res[i], a[i] + maxb[ni]);
res[i] = max(res[i], b[i] + maxa[ni]);
}
res[0] = max(res[0], a[0] + b[0] - 1);
// for (int i=0; i<D; i++){
// cout<<b[i]<<' ';
// }
// cout<<"\n\n\n";
for (int i=D-2; i>=0; i--) res[i] = max(res[i+1], res[i]);
return res;
}
int smallDFS(int i, int p){
int ans = 0;
dp[i].resize(D,0);
for (int c: adj[i]){
if (c==p) continue;
smallDFS(c, i);
int tmp = dp[c][D-1];
for (int j=D-1; j>0; j--) dp[c][j] = dp[c][j-1]; dp[c][0] = tmp+1;
dp[i] = smallMerge(dp[i], dp[c]);
}
if (adj[i].size()==1 && i) dp[i][0] = 1;
for (int j=0; j<D; j++) ans = max(ans, dp[i][j]);
// cout<<i<<'\n';
// for (int j=0; j<D; j++) cout<<dp[i][j]<<' '; cout<<'\n';
return ans;
}
int smallD(){
return smallDFS(0,0);
}
int main(){
cin>>N>>D;
for (int i=1; i<N; i++){
int a; cin>>a;
adj[a].push_back(i); adj[i].push_back(a);
}
cout<<smallD()<<'\n';
}
Compilation message
catinatree.cpp: In function 'int smallDFS(int, int)':
catinatree.cpp:47:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
47 | for (int j=D-1; j>0; j--) dp[c][j] = dp[c][j-1]; dp[c][0] = tmp+1;
| ^~~
catinatree.cpp:47:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
47 | for (int j=D-1; j>0; j--) dp[c][j] = dp[c][j-1]; dp[c][0] = tmp+1;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 2 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 3 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 4 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 5 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 6 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 7 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 8 |
Correct |
2 ms |
9816 KB |
Output is correct |
| 9 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 10 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 11 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 12 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 13 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 14 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 15 |
Correct |
2 ms |
9816 KB |
Output is correct |
| 16 |
Correct |
2 ms |
10072 KB |
Output is correct |
| 17 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 18 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 19 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 20 |
Correct |
2 ms |
9820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 2 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 3 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 4 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 5 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 6 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 7 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 8 |
Correct |
2 ms |
9816 KB |
Output is correct |
| 9 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 10 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 11 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 12 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 13 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 14 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 15 |
Correct |
2 ms |
9816 KB |
Output is correct |
| 16 |
Correct |
2 ms |
10072 KB |
Output is correct |
| 17 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 18 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 19 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 20 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 21 |
Correct |
29 ms |
15964 KB |
Output is correct |
| 22 |
Correct |
3 ms |
9816 KB |
Output is correct |
| 23 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 24 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 25 |
Correct |
3 ms |
9816 KB |
Output is correct |
| 26 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 27 |
Correct |
3 ms |
9908 KB |
Output is correct |
| 28 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 29 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 30 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 31 |
Correct |
4 ms |
10076 KB |
Output is correct |
| 32 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 33 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 34 |
Correct |
4 ms |
10076 KB |
Output is correct |
| 35 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 36 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 37 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 38 |
Correct |
4 ms |
10076 KB |
Output is correct |
| 39 |
Correct |
4 ms |
10332 KB |
Output is correct |
| 40 |
Correct |
3 ms |
10076 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 2 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 3 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 4 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 5 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 6 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 7 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 8 |
Correct |
2 ms |
9816 KB |
Output is correct |
| 9 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 10 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 11 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 12 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 13 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 14 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 15 |
Correct |
2 ms |
9816 KB |
Output is correct |
| 16 |
Correct |
2 ms |
10072 KB |
Output is correct |
| 17 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 18 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 19 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 20 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 21 |
Correct |
29 ms |
15964 KB |
Output is correct |
| 22 |
Correct |
3 ms |
9816 KB |
Output is correct |
| 23 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 24 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 25 |
Correct |
3 ms |
9816 KB |
Output is correct |
| 26 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 27 |
Correct |
3 ms |
9908 KB |
Output is correct |
| 28 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 29 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 30 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 31 |
Correct |
4 ms |
10076 KB |
Output is correct |
| 32 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 33 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 34 |
Correct |
4 ms |
10076 KB |
Output is correct |
| 35 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 36 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 37 |
Correct |
3 ms |
9820 KB |
Output is correct |
| 38 |
Correct |
4 ms |
10076 KB |
Output is correct |
| 39 |
Correct |
4 ms |
10332 KB |
Output is correct |
| 40 |
Correct |
3 ms |
10076 KB |
Output is correct |
| 41 |
Correct |
93 ms |
21712 KB |
Output is correct |
| 42 |
Correct |
63 ms |
16720 KB |
Output is correct |
| 43 |
Correct |
91 ms |
22568 KB |
Output is correct |
| 44 |
Correct |
135 ms |
33208 KB |
Output is correct |
| 45 |
Correct |
234 ms |
53588 KB |
Output is correct |
| 46 |
Correct |
110 ms |
22336 KB |
Output is correct |
| 47 |
Correct |
268 ms |
50516 KB |
Output is correct |
| 48 |
Correct |
404 ms |
82000 KB |
Output is correct |
| 49 |
Correct |
775 ms |
175984 KB |
Output is correct |
| 50 |
Correct |
41 ms |
16464 KB |
Output is correct |
| 51 |
Correct |
51 ms |
18080 KB |
Output is correct |
| 52 |
Correct |
61 ms |
21076 KB |
Output is correct |
| 53 |
Correct |
101 ms |
23376 KB |
Output is correct |
| 54 |
Correct |
155 ms |
29620 KB |
Output is correct |
| 55 |
Correct |
147 ms |
32600 KB |
Output is correct |
| 56 |
Correct |
3 ms |
10072 KB |
Output is correct |
| 57 |
Correct |
626 ms |
180420 KB |
Output is correct |
| 58 |
Runtime error |
277 ms |
524288 KB |
Execution killed with signal 9 |
| 59 |
Halted |
0 ms |
0 KB |
- |
