# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
135697 | 2019-07-24T09:51:24 Z | khsoo01 | Cat in a tree (BOI17_catinatree) | C++11 | 591 ms | 173944 KB |
#include<bits/stdc++.h> using namespace std; const int N = 200005, B = 300; int n, d, ans; vector<int> dt[N], adj[N], tmp; void sol1 (int C) { dt[C].push_back(d); int S = 1; for(auto &T : adj[C]) { sol1(T); int M = 0; tmp.clear(); for(int i=0;i<dt[T].size();i++) { int D1 = dt[T][i] + 1; if(D1 >= d) M = max(M, i); for(int j=0;j<dt[C].size();j++) { int D2 = dt[C][j]; if(D1 + D2 >= d) { int V = min(D1, D2); if(tmp.size() <= i+j) tmp.push_back(V); else tmp[i+j] = max(tmp[i+j], min(D1, D2)); } } } for(int i=0;i<tmp.size();i++) { if(dt[C].size() <= i) dt[C].push_back(tmp[i]); else dt[C][i] = max(dt[C][i], tmp[i]); } S += M; } for(int i=dt[C].size();--i;) { dt[C][i-1] = max(dt[C][i-1], dt[C][i]); } if(dt[C].size() <= S) dt[C].push_back(0); } void sol2 (int C) { dt[C].resize(d); int S = 0; for(auto &T : adj[C]) {sol2(T); S += dt[T][d-1];} dt[C][0] = S + 1; for(int k=1;k<d;k++) { int M = 0; if(k >= d-k) { for(auto &T : adj[C]) dt[C][k] += dt[T][k-1]; } else { for(auto &T : adj[C]) { dt[C][k] += dt[T][d-k-1]; M = max(M, dt[T][k-1]-dt[T][d-k-1]); } dt[C][k] += M; } } for(int k=d;--k;) dt[C][k-1] = max(dt[C][k-1], dt[C][k]); } int main() { scanf("%d%d",&n,&d); for(int i=1;i<n;i++) { int T; scanf("%d",&T); adj[T].push_back(i); } if(d > B) {sol1(0); ans = (int)dt[0].size()-1;} else {sol2(0); ans = dt[0][0];} printf("%d\n",ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 9720 KB | Output is correct |
2 | Correct | 10 ms | 9720 KB | Output is correct |
3 | Correct | 12 ms | 9720 KB | Output is correct |
4 | Correct | 12 ms | 9720 KB | Output is correct |
5 | Correct | 12 ms | 9720 KB | Output is correct |
6 | Correct | 10 ms | 9720 KB | Output is correct |
7 | Correct | 10 ms | 9720 KB | Output is correct |
8 | Correct | 10 ms | 9720 KB | Output is correct |
9 | Correct | 13 ms | 9720 KB | Output is correct |
10 | Correct | 12 ms | 9720 KB | Output is correct |
11 | Correct | 13 ms | 9720 KB | Output is correct |
12 | Correct | 11 ms | 9720 KB | Output is correct |
13 | Correct | 11 ms | 9848 KB | Output is correct |
14 | Correct | 12 ms | 9720 KB | Output is correct |
15 | Correct | 11 ms | 9720 KB | Output is correct |
16 | Correct | 12 ms | 9692 KB | Output is correct |
17 | Correct | 10 ms | 9720 KB | Output is correct |
18 | Correct | 10 ms | 9720 KB | Output is correct |
19 | Correct | 10 ms | 9720 KB | Output is correct |
20 | Correct | 14 ms | 9720 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 9720 KB | Output is correct |
2 | Correct | 10 ms | 9720 KB | Output is correct |
3 | Correct | 12 ms | 9720 KB | Output is correct |
4 | Correct | 12 ms | 9720 KB | Output is correct |
5 | Correct | 12 ms | 9720 KB | Output is correct |
6 | Correct | 10 ms | 9720 KB | Output is correct |
7 | Correct | 10 ms | 9720 KB | Output is correct |
8 | Correct | 10 ms | 9720 KB | Output is correct |
9 | Correct | 13 ms | 9720 KB | Output is correct |
10 | Correct | 12 ms | 9720 KB | Output is correct |
11 | Correct | 13 ms | 9720 KB | Output is correct |
12 | Correct | 11 ms | 9720 KB | Output is correct |
13 | Correct | 11 ms | 9848 KB | Output is correct |
14 | Correct | 12 ms | 9720 KB | Output is correct |
15 | Correct | 11 ms | 9720 KB | Output is correct |
16 | Correct | 12 ms | 9692 KB | Output is correct |
17 | Correct | 10 ms | 9720 KB | Output is correct |
18 | Correct | 10 ms | 9720 KB | Output is correct |
19 | Correct | 10 ms | 9720 KB | Output is correct |
20 | Correct | 14 ms | 9720 KB | Output is correct |
21 | Correct | 11 ms | 9976 KB | Output is correct |
22 | Correct | 10 ms | 9720 KB | Output is correct |
23 | Correct | 10 ms | 9720 KB | Output is correct |
24 | Correct | 10 ms | 9720 KB | Output is correct |
25 | Correct | 10 ms | 9724 KB | Output is correct |
26 | Correct | 10 ms | 9720 KB | Output is correct |
27 | Correct | 11 ms | 9820 KB | Output is correct |
28 | Correct | 11 ms | 9820 KB | Output is correct |
29 | Correct | 11 ms | 9848 KB | Output is correct |
30 | Correct | 11 ms | 9848 KB | Output is correct |
31 | Correct | 11 ms | 9976 KB | Output is correct |
32 | Correct | 11 ms | 9724 KB | Output is correct |
33 | Correct | 10 ms | 9720 KB | Output is correct |
34 | Correct | 10 ms | 9720 KB | Output is correct |
35 | Correct | 13 ms | 9848 KB | Output is correct |
36 | Correct | 11 ms | 9848 KB | Output is correct |
37 | Correct | 12 ms | 9720 KB | Output is correct |
38 | Correct | 12 ms | 10104 KB | Output is correct |
39 | Correct | 15 ms | 10232 KB | Output is correct |
40 | Correct | 13 ms | 9976 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 9720 KB | Output is correct |
2 | Correct | 10 ms | 9720 KB | Output is correct |
3 | Correct | 12 ms | 9720 KB | Output is correct |
4 | Correct | 12 ms | 9720 KB | Output is correct |
5 | Correct | 12 ms | 9720 KB | Output is correct |
6 | Correct | 10 ms | 9720 KB | Output is correct |
7 | Correct | 10 ms | 9720 KB | Output is correct |
8 | Correct | 10 ms | 9720 KB | Output is correct |
9 | Correct | 13 ms | 9720 KB | Output is correct |
10 | Correct | 12 ms | 9720 KB | Output is correct |
11 | Correct | 13 ms | 9720 KB | Output is correct |
12 | Correct | 11 ms | 9720 KB | Output is correct |
13 | Correct | 11 ms | 9848 KB | Output is correct |
14 | Correct | 12 ms | 9720 KB | Output is correct |
15 | Correct | 11 ms | 9720 KB | Output is correct |
16 | Correct | 12 ms | 9692 KB | Output is correct |
17 | Correct | 10 ms | 9720 KB | Output is correct |
18 | Correct | 10 ms | 9720 KB | Output is correct |
19 | Correct | 10 ms | 9720 KB | Output is correct |
20 | Correct | 14 ms | 9720 KB | Output is correct |
21 | Correct | 11 ms | 9976 KB | Output is correct |
22 | Correct | 10 ms | 9720 KB | Output is correct |
23 | Correct | 10 ms | 9720 KB | Output is correct |
24 | Correct | 10 ms | 9720 KB | Output is correct |
25 | Correct | 10 ms | 9724 KB | Output is correct |
26 | Correct | 10 ms | 9720 KB | Output is correct |
27 | Correct | 11 ms | 9820 KB | Output is correct |
28 | Correct | 11 ms | 9820 KB | Output is correct |
29 | Correct | 11 ms | 9848 KB | Output is correct |
30 | Correct | 11 ms | 9848 KB | Output is correct |
31 | Correct | 11 ms | 9976 KB | Output is correct |
32 | Correct | 11 ms | 9724 KB | Output is correct |
33 | Correct | 10 ms | 9720 KB | Output is correct |
34 | Correct | 10 ms | 9720 KB | Output is correct |
35 | Correct | 13 ms | 9848 KB | Output is correct |
36 | Correct | 11 ms | 9848 KB | Output is correct |
37 | Correct | 12 ms | 9720 KB | Output is correct |
38 | Correct | 12 ms | 10104 KB | Output is correct |
39 | Correct | 15 ms | 10232 KB | Output is correct |
40 | Correct | 13 ms | 9976 KB | Output is correct |
41 | Correct | 110 ms | 20368 KB | Output is correct |
42 | Correct | 65 ms | 15088 KB | Output is correct |
43 | Correct | 89 ms | 21240 KB | Output is correct |
44 | Correct | 146 ms | 32156 KB | Output is correct |
45 | Correct | 196 ms | 52596 KB | Output is correct |
46 | Correct | 152 ms | 20344 KB | Output is correct |
47 | Correct | 272 ms | 48528 KB | Output is correct |
48 | Correct | 352 ms | 79992 KB | Output is correct |
49 | Correct | 591 ms | 173944 KB | Output is correct |
50 | Correct | 44 ms | 13820 KB | Output is correct |
51 | Correct | 52 ms | 15352 KB | Output is correct |
52 | Correct | 62 ms | 18424 KB | Output is correct |
53 | Correct | 82 ms | 17784 KB | Output is correct |
54 | Correct | 124 ms | 23980 KB | Output is correct |
55 | Correct | 128 ms | 27228 KB | Output is correct |
56 | Correct | 11 ms | 9848 KB | Output is correct |
57 | Correct | 23 ms | 14456 KB | Output is correct |
58 | Correct | 74 ms | 30712 KB | Output is correct |
59 | Correct | 150 ms | 36344 KB | Output is correct |
60 | Correct | 88 ms | 24180 KB | Output is correct |
61 | Correct | 503 ms | 166620 KB | Output is correct |