# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
767310 | 2023-06-26T15:27:31 Z | PoonYaPat | Cat in a tree (BOI17_catinatree) | C++14 | 255 ms | 244260 KB |
#include <bits/stdc++.h> using namespace std; int n,d; vector<int> adj[200001]; deque<int> temp[200001]; void dfs(int x) { for (auto s : adj[x]) dfs(s); if (adj[x].size()==0) temp[x].push_front(1); else { int sum=1; if (temp[adj[x][0]].size()>=d) sum+=temp[adj[x][0]][d-1]; swap(temp[x],temp[adj[x][0]]); for (int j=1; j<adj[x].size(); ++j) { int c=adj[x][j]; if (temp[c].size()>=d) sum+=temp[c][d-1]; if (temp[x].size()<temp[c].size()) swap(temp[x],temp[c]); for (int i=0; i<temp[c].size(); ++i) { if (2*(i+1)<d) { if (temp[c].size()>=d-i-1) temp[x][i]=max(temp[x][i]+temp[c][d-2-i],temp[c][i]+temp[x][d-2-i]); else if (temp[x].size()>=d-i-1) temp[x][i]=max(temp[x][i],temp[c][i]+temp[x][d-2-i]); else temp[x][i]=max(temp[x][i],temp[c][i]); } else temp[x][i]+=temp[c][i]; } for (int i=min((int)(temp[x].size())-2,(int)(temp[c].size())-1); i>=0; --i) temp[x][i]=max(temp[x][i],temp[x][i+1]); } temp[x].push_front(max(sum,temp[x][0])); } while (temp[x].size()>d) temp[x].pop_back(); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n>>d; for (int i=1; i<n; ++i) { int x; cin>>x; adj[x].push_back(i); } dfs(0); cout<<temp[0].front(); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 69 ms | 139596 KB | Output is correct |
2 | Correct | 65 ms | 139632 KB | Output is correct |
3 | Correct | 65 ms | 139640 KB | Output is correct |
4 | Correct | 68 ms | 139640 KB | Output is correct |
5 | Correct | 65 ms | 139608 KB | Output is correct |
6 | Correct | 67 ms | 139596 KB | Output is correct |
7 | Correct | 66 ms | 139576 KB | Output is correct |
8 | Correct | 67 ms | 139640 KB | Output is correct |
9 | Correct | 66 ms | 139508 KB | Output is correct |
10 | Correct | 68 ms | 139600 KB | Output is correct |
11 | Correct | 66 ms | 139596 KB | Output is correct |
12 | Correct | 65 ms | 139536 KB | Output is correct |
13 | Correct | 67 ms | 139540 KB | Output is correct |
14 | Correct | 66 ms | 139568 KB | Output is correct |
15 | Correct | 67 ms | 139648 KB | Output is correct |
16 | Correct | 66 ms | 139640 KB | Output is correct |
17 | Correct | 66 ms | 139628 KB | Output is correct |
18 | Correct | 65 ms | 139548 KB | Output is correct |
19 | Correct | 70 ms | 139648 KB | Output is correct |
20 | Correct | 76 ms | 139532 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 69 ms | 139596 KB | Output is correct |
2 | Correct | 65 ms | 139632 KB | Output is correct |
3 | Correct | 65 ms | 139640 KB | Output is correct |
4 | Correct | 68 ms | 139640 KB | Output is correct |
5 | Correct | 65 ms | 139608 KB | Output is correct |
6 | Correct | 67 ms | 139596 KB | Output is correct |
7 | Correct | 66 ms | 139576 KB | Output is correct |
8 | Correct | 67 ms | 139640 KB | Output is correct |
9 | Correct | 66 ms | 139508 KB | Output is correct |
10 | Correct | 68 ms | 139600 KB | Output is correct |
11 | Correct | 66 ms | 139596 KB | Output is correct |
12 | Correct | 65 ms | 139536 KB | Output is correct |
13 | Correct | 67 ms | 139540 KB | Output is correct |
14 | Correct | 66 ms | 139568 KB | Output is correct |
15 | Correct | 67 ms | 139648 KB | Output is correct |
16 | Correct | 66 ms | 139640 KB | Output is correct |
17 | Correct | 66 ms | 139628 KB | Output is correct |
18 | Correct | 65 ms | 139548 KB | Output is correct |
19 | Correct | 70 ms | 139648 KB | Output is correct |
20 | Correct | 76 ms | 139532 KB | Output is correct |
21 | Correct | 67 ms | 139840 KB | Output is correct |
22 | Correct | 72 ms | 139596 KB | Output is correct |
23 | Correct | 72 ms | 139668 KB | Output is correct |
24 | Correct | 81 ms | 139768 KB | Output is correct |
25 | Correct | 78 ms | 139712 KB | Output is correct |
26 | Correct | 73 ms | 139800 KB | Output is correct |
27 | Correct | 74 ms | 139876 KB | Output is correct |
28 | Correct | 80 ms | 139980 KB | Output is correct |
29 | Correct | 75 ms | 139928 KB | Output is correct |
30 | Correct | 84 ms | 140092 KB | Output is correct |
31 | Correct | 77 ms | 139972 KB | Output is correct |
32 | Correct | 74 ms | 140364 KB | Output is correct |
33 | Correct | 75 ms | 140364 KB | Output is correct |
34 | Correct | 76 ms | 140260 KB | Output is correct |
35 | Correct | 73 ms | 140220 KB | Output is correct |
36 | Correct | 80 ms | 140372 KB | Output is correct |
37 | Correct | 83 ms | 140392 KB | Output is correct |
38 | Correct | 73 ms | 140212 KB | Output is correct |
39 | Correct | 74 ms | 140152 KB | Output is correct |
40 | Correct | 73 ms | 139852 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 69 ms | 139596 KB | Output is correct |
2 | Correct | 65 ms | 139632 KB | Output is correct |
3 | Correct | 65 ms | 139640 KB | Output is correct |
4 | Correct | 68 ms | 139640 KB | Output is correct |
5 | Correct | 65 ms | 139608 KB | Output is correct |
6 | Correct | 67 ms | 139596 KB | Output is correct |
7 | Correct | 66 ms | 139576 KB | Output is correct |
8 | Correct | 67 ms | 139640 KB | Output is correct |
9 | Correct | 66 ms | 139508 KB | Output is correct |
10 | Correct | 68 ms | 139600 KB | Output is correct |
11 | Correct | 66 ms | 139596 KB | Output is correct |
12 | Correct | 65 ms | 139536 KB | Output is correct |
13 | Correct | 67 ms | 139540 KB | Output is correct |
14 | Correct | 66 ms | 139568 KB | Output is correct |
15 | Correct | 67 ms | 139648 KB | Output is correct |
16 | Correct | 66 ms | 139640 KB | Output is correct |
17 | Correct | 66 ms | 139628 KB | Output is correct |
18 | Correct | 65 ms | 139548 KB | Output is correct |
19 | Correct | 70 ms | 139648 KB | Output is correct |
20 | Correct | 76 ms | 139532 KB | Output is correct |
21 | Correct | 67 ms | 139840 KB | Output is correct |
22 | Correct | 72 ms | 139596 KB | Output is correct |
23 | Correct | 72 ms | 139668 KB | Output is correct |
24 | Correct | 81 ms | 139768 KB | Output is correct |
25 | Correct | 78 ms | 139712 KB | Output is correct |
26 | Correct | 73 ms | 139800 KB | Output is correct |
27 | Correct | 74 ms | 139876 KB | Output is correct |
28 | Correct | 80 ms | 139980 KB | Output is correct |
29 | Correct | 75 ms | 139928 KB | Output is correct |
30 | Correct | 84 ms | 140092 KB | Output is correct |
31 | Correct | 77 ms | 139972 KB | Output is correct |
32 | Correct | 74 ms | 140364 KB | Output is correct |
33 | Correct | 75 ms | 140364 KB | Output is correct |
34 | Correct | 76 ms | 140260 KB | Output is correct |
35 | Correct | 73 ms | 140220 KB | Output is correct |
36 | Correct | 80 ms | 140372 KB | Output is correct |
37 | Correct | 83 ms | 140392 KB | Output is correct |
38 | Correct | 73 ms | 140212 KB | Output is correct |
39 | Correct | 74 ms | 140152 KB | Output is correct |
40 | Correct | 73 ms | 139852 KB | Output is correct |
41 | Correct | 165 ms | 183112 KB | Output is correct |
42 | Correct | 139 ms | 154684 KB | Output is correct |
43 | Correct | 146 ms | 167636 KB | Output is correct |
44 | Correct | 142 ms | 167600 KB | Output is correct |
45 | Correct | 139 ms | 167484 KB | Output is correct |
46 | Correct | 227 ms | 182280 KB | Output is correct |
47 | Correct | 245 ms | 195584 KB | Output is correct |
48 | Correct | 233 ms | 195712 KB | Output is correct |
49 | Correct | 255 ms | 195780 KB | Output is correct |
50 | Correct | 122 ms | 191684 KB | Output is correct |
51 | Correct | 128 ms | 191744 KB | Output is correct |
52 | Correct | 124 ms | 191732 KB | Output is correct |
53 | Correct | 187 ms | 244132 KB | Output is correct |
54 | Correct | 186 ms | 244220 KB | Output is correct |
55 | Correct | 189 ms | 244260 KB | Output is correct |
56 | Correct | 80 ms | 140512 KB | Output is correct |
57 | Correct | 78 ms | 144128 KB | Output is correct |
58 | Correct | 100 ms | 162320 KB | Output is correct |
59 | Correct | 177 ms | 211372 KB | Output is correct |
60 | Correct | 154 ms | 178324 KB | Output is correct |
61 | Correct | 161 ms | 177612 KB | Output is correct |