#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define per(i, a, b) for (int i = b - 1; i >= a; --i)
#define trav(x, a) for (auto& x : a)
typedef pair<int, int> ii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
vi graph[1501];
int d, memo[1501][1501];
int dp(int u, int dist) {
int& ans = memo[u][dist];
if (ans != -1) return ans;
ans = 0;
if (!dist) {
ans = 1;
trav(v, graph[u]) ans += dp(v, d - 1);
}
int i = max(0, dist);
while (1) {
int j = max(dist, d - i), sum = 0;
if (j < i) break;
trav(v, graph[u]) sum += dp(v, j - 1);
trav(v, graph[u]) ans = max(ans, sum - memo[v][j - 1] + dp(v, i - 1));
++i;
}
return ans;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
memset(memo, -1, sizeof(memo));
int n, p;
cin >> n >> d;
d = min(d, n);
if (1500 < n) return 0;
rep(i, 1, n) {
cin >> p;
graph[p].push_back(i);
}
cout << dp(0, 0) << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9164 KB |
Output is correct |
2 |
Correct |
5 ms |
9164 KB |
Output is correct |
3 |
Correct |
4 ms |
9168 KB |
Output is correct |
4 |
Correct |
4 ms |
9172 KB |
Output is correct |
5 |
Correct |
5 ms |
9164 KB |
Output is correct |
6 |
Correct |
5 ms |
9060 KB |
Output is correct |
7 |
Correct |
5 ms |
9164 KB |
Output is correct |
8 |
Correct |
5 ms |
9164 KB |
Output is correct |
9 |
Correct |
6 ms |
9164 KB |
Output is correct |
10 |
Correct |
5 ms |
9164 KB |
Output is correct |
11 |
Correct |
5 ms |
9164 KB |
Output is correct |
12 |
Correct |
5 ms |
9164 KB |
Output is correct |
13 |
Correct |
5 ms |
9172 KB |
Output is correct |
14 |
Correct |
5 ms |
9164 KB |
Output is correct |
15 |
Correct |
4 ms |
9164 KB |
Output is correct |
16 |
Correct |
5 ms |
9148 KB |
Output is correct |
17 |
Correct |
4 ms |
9172 KB |
Output is correct |
18 |
Correct |
4 ms |
9164 KB |
Output is correct |
19 |
Correct |
5 ms |
9164 KB |
Output is correct |
20 |
Correct |
5 ms |
9164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9164 KB |
Output is correct |
2 |
Correct |
5 ms |
9164 KB |
Output is correct |
3 |
Correct |
4 ms |
9168 KB |
Output is correct |
4 |
Correct |
4 ms |
9172 KB |
Output is correct |
5 |
Correct |
5 ms |
9164 KB |
Output is correct |
6 |
Correct |
5 ms |
9060 KB |
Output is correct |
7 |
Correct |
5 ms |
9164 KB |
Output is correct |
8 |
Correct |
5 ms |
9164 KB |
Output is correct |
9 |
Correct |
6 ms |
9164 KB |
Output is correct |
10 |
Correct |
5 ms |
9164 KB |
Output is correct |
11 |
Correct |
5 ms |
9164 KB |
Output is correct |
12 |
Correct |
5 ms |
9164 KB |
Output is correct |
13 |
Correct |
5 ms |
9172 KB |
Output is correct |
14 |
Correct |
5 ms |
9164 KB |
Output is correct |
15 |
Correct |
4 ms |
9164 KB |
Output is correct |
16 |
Correct |
5 ms |
9148 KB |
Output is correct |
17 |
Correct |
4 ms |
9172 KB |
Output is correct |
18 |
Correct |
4 ms |
9164 KB |
Output is correct |
19 |
Correct |
5 ms |
9164 KB |
Output is correct |
20 |
Correct |
5 ms |
9164 KB |
Output is correct |
21 |
Execution timed out |
1091 ms |
9308 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9164 KB |
Output is correct |
2 |
Correct |
5 ms |
9164 KB |
Output is correct |
3 |
Correct |
4 ms |
9168 KB |
Output is correct |
4 |
Correct |
4 ms |
9172 KB |
Output is correct |
5 |
Correct |
5 ms |
9164 KB |
Output is correct |
6 |
Correct |
5 ms |
9060 KB |
Output is correct |
7 |
Correct |
5 ms |
9164 KB |
Output is correct |
8 |
Correct |
5 ms |
9164 KB |
Output is correct |
9 |
Correct |
6 ms |
9164 KB |
Output is correct |
10 |
Correct |
5 ms |
9164 KB |
Output is correct |
11 |
Correct |
5 ms |
9164 KB |
Output is correct |
12 |
Correct |
5 ms |
9164 KB |
Output is correct |
13 |
Correct |
5 ms |
9172 KB |
Output is correct |
14 |
Correct |
5 ms |
9164 KB |
Output is correct |
15 |
Correct |
4 ms |
9164 KB |
Output is correct |
16 |
Correct |
5 ms |
9148 KB |
Output is correct |
17 |
Correct |
4 ms |
9172 KB |
Output is correct |
18 |
Correct |
4 ms |
9164 KB |
Output is correct |
19 |
Correct |
5 ms |
9164 KB |
Output is correct |
20 |
Correct |
5 ms |
9164 KB |
Output is correct |
21 |
Execution timed out |
1091 ms |
9308 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |