#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn5 = 2e3 + 10;
int d;
int dp[maxn5][maxn5];
int tmp[maxn5], sz[maxn5];
vector <int> adj[maxn5];
inline void dfs(int v){
sz[v] = 1;
for(auto u : adj[v]){
dfs(u);
memset(tmp, 0, sizeof tmp);
for(int i = 0; i <= sz[u]; i++) for(int j = 0; j <= sz[v]; j++) if(i + 1 + j >= d){
tmp[min(i + 1, j)] = max(tmp[min(i + 1, j)], dp[v][j] + dp[u][i]);
}
for(int i = 0; i <= sz[u]; i++)
tmp[i + 1] = max(tmp[i + 1], dp[u][i]);
sz[v] += sz[u];
for(int i = 0; i <= sz[v]; i++){
dp[v][i] = max(dp[v][i], tmp[i]);
//cout << "se of " << v << ' '<< u << ' ' << i << ' ' << dp[v][i] << ' ' << tmp[i] << endl;
}
}
dp[v][0] = max(dp[v][0], dp[v][d] + 1);
//for(int i = 0; i <= d; i++)
//cout << v << ' '<< i << ' '<< dp[v][i] << endl;
return;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n; cin >> n >> d;
for(int i = 1; i < n; i++){
int a; cin >> a;
adj[a].pb(i);
}
dfs(0);
int ans = *max_element(dp[0], dp[0] + n + 5);
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
380 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
380 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
380 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
380 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
380 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
380 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
380 KB |
Output is correct |
21 |
Correct |
14 ms |
10452 KB |
Output is correct |
22 |
Correct |
2 ms |
2388 KB |
Output is correct |
23 |
Correct |
2 ms |
2388 KB |
Output is correct |
24 |
Correct |
2 ms |
2388 KB |
Output is correct |
25 |
Correct |
5 ms |
4436 KB |
Output is correct |
26 |
Correct |
5 ms |
4436 KB |
Output is correct |
27 |
Correct |
5 ms |
4348 KB |
Output is correct |
28 |
Correct |
8 ms |
6484 KB |
Output is correct |
29 |
Correct |
9 ms |
6408 KB |
Output is correct |
30 |
Correct |
8 ms |
6356 KB |
Output is correct |
31 |
Correct |
9 ms |
6488 KB |
Output is correct |
32 |
Correct |
9 ms |
6228 KB |
Output is correct |
33 |
Correct |
10 ms |
6268 KB |
Output is correct |
34 |
Correct |
9 ms |
6016 KB |
Output is correct |
35 |
Correct |
9 ms |
5972 KB |
Output is correct |
36 |
Correct |
8 ms |
6388 KB |
Output is correct |
37 |
Correct |
14 ms |
6592 KB |
Output is correct |
38 |
Correct |
13 ms |
7124 KB |
Output is correct |
39 |
Correct |
12 ms |
7764 KB |
Output is correct |
40 |
Correct |
13 ms |
10452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
380 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
380 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
380 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
384 KB |
Output is correct |
20 |
Correct |
1 ms |
380 KB |
Output is correct |
21 |
Correct |
14 ms |
10452 KB |
Output is correct |
22 |
Correct |
2 ms |
2388 KB |
Output is correct |
23 |
Correct |
2 ms |
2388 KB |
Output is correct |
24 |
Correct |
2 ms |
2388 KB |
Output is correct |
25 |
Correct |
5 ms |
4436 KB |
Output is correct |
26 |
Correct |
5 ms |
4436 KB |
Output is correct |
27 |
Correct |
5 ms |
4348 KB |
Output is correct |
28 |
Correct |
8 ms |
6484 KB |
Output is correct |
29 |
Correct |
9 ms |
6408 KB |
Output is correct |
30 |
Correct |
8 ms |
6356 KB |
Output is correct |
31 |
Correct |
9 ms |
6488 KB |
Output is correct |
32 |
Correct |
9 ms |
6228 KB |
Output is correct |
33 |
Correct |
10 ms |
6268 KB |
Output is correct |
34 |
Correct |
9 ms |
6016 KB |
Output is correct |
35 |
Correct |
9 ms |
5972 KB |
Output is correct |
36 |
Correct |
8 ms |
6388 KB |
Output is correct |
37 |
Correct |
14 ms |
6592 KB |
Output is correct |
38 |
Correct |
13 ms |
7124 KB |
Output is correct |
39 |
Correct |
12 ms |
7764 KB |
Output is correct |
40 |
Correct |
13 ms |
10452 KB |
Output is correct |
41 |
Runtime error |
42 ms |
18036 KB |
Execution killed with signal 11 |
42 |
Halted |
0 ms |
0 KB |
- |