QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#414650 | #33. Cat in a tree | x-camp | 51 | 3ms | 10912kb | C++17 | 1.2kb | 2024-05-19 13:38:05 | 2024-05-19 13:38:06 |
Judging History
answer
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <set>
#include <cstring>
#include <queue>
#define MX 200002
using namespace std;
vector<int> adj[MX];
int N,D;
int dep[MX];
set<pair<int,int>> nodes;
set<pair<int,int>>::iterator ptr[MX];
bool removed[MX];
void dfs(int u, int par, int depth) {
dep[u] = depth;
auto it = nodes.insert({depth,u}).first;
ptr[u] = it;
for (auto v: adj[u]) {
if (v != par) {
dfs(v, u, depth+1);
}
}
}
void dfs_maxD(int u, int par, int depth) {
if (depth >= D ) {
return;
}
for (auto v: adj[u]) {
if (v != par) {
dfs_maxD(v, u, depth+1);
}
}
if (!removed[u]) {
nodes.erase({dep[u],u});
removed[u] = true;
}
}
int main() {
cin >> N >> D;
for (int i=1; i<N; i++) {
int a;
cin >> a;
adj[i].push_back(a);
adj[a].push_back(i);
}
dfs(0,-1, 0);
int ans = 0;
while (!nodes.empty()) {
auto &[d, node] = *nodes.rbegin();
dfs_maxD(node, -1, 0);
ans++;
}
cout << ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 11
Accepted
Test #1:
score: 11
Accepted
time: 2ms
memory: 10664kb
input:
10 2 0 0 2 2 0 3 4 7 2
output:
6
result:
ok single line: '6'
Test #2:
score: 11
Accepted
time: 0ms
memory: 10672kb
input:
10 3 0 0 2 1 4 4 3 1 7
output:
4
result:
ok single line: '4'
Test #3:
score: 11
Accepted
time: 2ms
memory: 10620kb
input:
12 1 0 0 1 3 1 0 2 1 3 2 2
output:
12
result:
ok single line: '12'
Test #4:
score: 11
Accepted
time: 3ms
memory: 10556kb
input:
12 4 0 0 1 2 0 0 4 7 7 9 10
output:
3
result:
ok single line: '3'
Test #5:
score: 11
Accepted
time: 0ms
memory: 10560kb
input:
14 2 0 1 2 3 0 1 5 1 4 0 3 11 9
output:
8
result:
ok single line: '8'
Test #6:
score: 11
Accepted
time: 2ms
memory: 10496kb
input:
14 4 0 0 2 3 4 2 6 3 6 9 3 3 2
output:
3
result:
ok single line: '3'
Test #7:
score: 11
Accepted
time: 0ms
memory: 10624kb
input:
16 2 0 0 0 1 2 3 2 6 6 0 4 11 0 12 2
output:
11
result:
ok single line: '11'
Test #8:
score: 11
Accepted
time: 3ms
memory: 10616kb
input:
16 3 0 0 0 3 2 2 0 2 8 4 6 11 8 3 5
output:
6
result:
ok single line: '6'
Test #9:
score: 11
Accepted
time: 2ms
memory: 10672kb
input:
18 1 0 0 2 2 2 1 0 3 1 4 2 2 12 0 6 10 13
output:
18
result:
ok single line: '18'
Test #10:
score: 11
Accepted
time: 0ms
memory: 10668kb
input:
18 5 0 0 2 1 0 2 6 5 8 5 0 8 5 4 12 7 10
output:
4
result:
ok single line: '4'
Test #11:
score: 11
Accepted
time: 0ms
memory: 10264kb
input:
18 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
18
result:
ok single line: '18'
Test #12:
score: 11
Accepted
time: 2ms
memory: 10676kb
input:
18 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output:
17
result:
ok single line: '17'
Test #13:
score: 11
Accepted
time: 0ms
memory: 10780kb
input:
17 1 0 1 1 0 0 1 2 0 1 0 2 1 2 2 2 2
output:
17
result:
ok single line: '17'
Test #14:
score: 11
Accepted
time: 0ms
memory: 10552kb
input:
17 2 0 1 0 1 1 0 2 1 2 1 1 0 1 2 0 0
output:
14
result:
ok single line: '14'
Test #15:
score: 11
Accepted
time: 0ms
memory: 10572kb
input:
18 5 0 0 1 1 0 1 2 2 2 1 0 0 1 0 1 1 0
output:
1
result:
ok single line: '1'
Test #16:
score: 11
Accepted
time: 3ms
memory: 10608kb
input:
18 1 0 1 2 0 1 0 4 0 2 3 0 3 2 1 3 4 2
output:
18
result:
ok single line: '18'
Test #17:
score: 11
Accepted
time: 0ms
memory: 10608kb
input:
18 2 0 0 0 1 2 2 3 3 1 3 4 1 1 4 2 4 0
output:
13
result:
ok single line: '13'
Test #18:
score: 11
Accepted
time: 0ms
memory: 10564kb
input:
18 3 0 1 1 3 1 4 2 1 0 2 0 0 1 1 3 0 3
output:
5
result:
ok single line: '5'
Test #19:
score: 11
Accepted
time: 2ms
memory: 10620kb
input:
18 6 0 0 2 3 4 3 3 1 6 1 2 0 2 0 5 2 4
output:
2
result:
ok single line: '2'
Test #20:
score: 11
Accepted
time: 0ms
memory: 10684kb
input:
18 7 0 1 0 3 2 0 6 3 4 4 3 2 6 3 6 0 0
output:
1
result:
ok single line: '1'
Subtask #2:
score: 40
Accepted
Dependency #1:
100%
Accepted
Test #21:
score: 40
Accepted
time: 0ms
memory: 10912kb
input:
1500 1000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 ...
output:
2
result:
ok single line: '2'
Test #22:
score: 40
Accepted
time: 2ms
memory: 10600kb
input:
500 1 0 1 1 1 1 5 5 2 4 4 10 0 0 11 12 6 13 5 17 2 13 12 19 12 8 7 18 5 9 10 15 1 25 21 7 32 29 14 22 12 34 13 1 10 0 20 4 6 44 38 19 12 9 17 20 51 5 3 23 46 39 25 7 42 37 55 13 14 30 46 9 71 47 55 61 43 39 1 76 0 49 8 80 51 51 71 55 44 79 25 80 24 68 15 41 88 72 76 72 38 83 94 88 69 17 9 49 75 64 3...
output:
500
result:
ok single line: '500'
Test #23:
score: 40
Accepted
time: 0ms
memory: 10584kb
input:
500 5 0 1 2 0 3 5 0 2 0 3 10 1 3 5 13 8 8 16 16 4 17 5 1 17 6 1 17 9 20 0 27 27 1 14 24 30 17 5 37 37 9 33 7 20 39 24 29 20 33 19 32 26 13 33 31 21 31 11 20 50 35 34 16 47 17 5 48 55 60 66 57 43 10 68 69 69 34 75 27 41 3 56 8 32 41 85 55 70 5 57 48 61 41 78 19 12 85 73 62 18 79 95 47 39 61 67 88 18 ...
output:
89
result:
ok single line: '89'
Test #24:
score: 40
Accepted
time: 0ms
memory: 10408kb
input:
500 10 0 1 1 0 1 0 6 6 8 1 4 0 10 0 13 8 11 16 18 1 17 7 21 22 1 22 9 26 1 4 1 21 5 18 6 7 35 4 31 5 38 36 31 37 25 17 8 28 36 12 26 20 9 11 20 42 38 17 29 42 29 38 28 39 46 39 3 46 22 16 34 25 14 3 21 73 62 77 78 29 43 3 25 48 3 47 17 54 3 43 47 43 42 62 12 44 38 29 75 62 37 96 91 47 97 104 15 84 4...
output:
23
result:
ok single line: '23'
Test #25:
score: 40
Accepted
time: 2ms
memory: 10872kb
input:
1000 1 0 0 0 2 0 4 3 4 4 2 9 4 1 12 2 12 7 12 13 1 12 20 17 5 8 3 7 0 11 18 28 2 29 26 34 24 5 24 22 38 30 0 30 19 17 9 45 32 14 47 42 29 47 5 2 1 44 23 16 48 3 51 28 44 16 24 31 8 49 0 6 12 39 6 13 2 74 77 0 25 78 67 43 83 32 22 69 38 57 32 62 23 12 22 53 85 88 91 3 4 42 96 93 20 59 44 59 102 95 86...
output:
1000
result:
ok single line: '1000'
Test #26:
score: 40
Accepted
time: 0ms
memory: 10632kb
input:
1000 5 0 0 1 1 2 3 0 2 0 1 6 3 10 13 14 1 12 0 2 0 0 16 0 14 13 11 1 4 2 15 21 10 24 4 0 18 16 29 24 2 38 40 17 31 17 30 8 18 12 49 16 47 31 52 53 10 41 28 39 57 20 49 43 1 46 27 59 38 7 37 24 38 36 13 59 34 25 31 63 36 4 32 72 9 17 4 80 87 63 20 68 43 42 64 80 8 88 2 24 68 6 41 34 68 63 66 92 32 93...
output:
191
result:
ok single line: '191'
Test #27:
score: 40
Accepted
time: 0ms
memory: 10676kb
input:
1000 10 0 0 1 2 2 2 4 2 3 9 10 5 7 3 4 6 7 2 8 16 9 5 4 3 17 17 23 10 11 26 15 30 20 32 27 12 5 29 10 15 22 9 40 19 30 1 23 33 16 5 0 5 18 18 5 48 5 50 27 39 35 60 54 11 29 25 43 13 62 29 48 39 13 49 44 66 52 65 54 29 66 15 32 35 76 7 53 40 57 7 7 77 82 83 43 31 28 85 69 1 9 72 32 29 53 57 5 94 57 6...
output:
44
result:
ok single line: '44'
Test #28:
score: 40
Accepted
time: 3ms
memory: 10504kb
input:
1500 12 0 1 2 0 4 2 0 4 6 2 3 10 4 2 12 2 10 1 5 7 7 10 3 10 0 20 1 15 24 25 0 10 30 13 0 14 24 20 7 37 25 6 20 34 37 0 27 28 25 26 28 8 2 25 50 19 19 55 33 26 53 1 53 23 20 23 27 36 17 63 22 39 10 22 26 68 62 26 1 56 11 1 51 12 19 84 42 59 65 73 9 61 63 65 27 44 34 85 31 79 98 72 60 57 92 10 53 45 ...
output:
41
result:
ok single line: '41'
Test #29:
score: 40
Accepted
time: 3ms
memory: 10676kb
input:
1500 5 0 0 2 2 3 0 5 0 0 6 2 8 0 12 8 0 2 5 4 4 4 0 0 10 16 4 26 27 10 17 23 21 5 24 27 6 22 28 2 38 24 11 38 25 19 20 22 35 21 7 6 42 21 19 30 30 56 10 23 31 5 35 49 25 2 28 31 56 43 65 55 62 15 45 10 70 30 56 67 28 35 56 4 25 42 34 41 76 12 81 66 66 8 57 47 80 75 14 68 97 12 58 10 75 86 64 101 104...
output:
293
result:
ok single line: '293'
Test #30:
score: 40
Accepted
time: 0ms
memory: 10728kb
input:
1500 15 0 1 2 3 0 0 5 1 8 0 10 1 1 0 4 6 4 2 5 18 1 8 3 8 3 1 20 22 23 28 25 31 3 28 27 8 36 25 3 30 8 29 41 21 41 34 46 37 24 6 33 15 44 44 18 14 37 55 43 59 10 3 40 27 55 44 40 3 22 53 18 11 17 35 1 41 53 41 22 40 29 35 21 26 37 23 38 74 33 84 2 63 82 53 45 24 43 75 1 66 80 52 63 31 63 46 71 65 48...
output:
19
result:
ok single line: '19'
Test #31:
score: 40
Accepted
time: 0ms
memory: 10420kb
input:
1500 40 0 1 0 0 1 1 0 7 2 5 1 9 11 9 12 3 14 8 10 11 3 5 16 5 9 20 18 21 17 8 30 13 28 9 9 30 9 2 9 6 25 28 8 33 43 19 37 41 14 10 44 38 8 53 47 1 46 32 14 24 23 51 14 46 32 32 66 60 49 53 45 35 47 24 72 52 56 22 77 65 23 3 61 33 36 48 12 79 21 46 74 9 24 23 25 36 2 63 95 49 45 68 18 51 16 1 29 48 1...
output:
1
result:
ok single line: '1'
Test #32:
score: 40
Accepted
time: 0ms
memory: 10804kb
input:
1470 4 0 0 1 1 3 4 1 2 5 8 2 8 11 11 9 5 1 0 11 19 8 7 6 1 9 3 13 0 0 16 14 11 12 11 19 14 13 1 12 5 2 6 18 17 12 18 3 7 11 3 15 7 4 19 17 14 17 6 3 11 16 8 3 4 3 7 3 4 17 7 9 7 8 15 6 10 19 12 17 10 10 2 3 4 8 7 4 5 9 1 17 12 10 0 2 13 3 5 4 19 15 10 9 6 7 13 7 5 1 17 18 6 11 12 5 4 17 15 5 0 16 4 ...
output:
13
result:
ok single line: '13'
Test #33:
score: 40
Accepted
time: 0ms
memory: 10752kb
input:
1470 10 0 1 2 1 0 3 2 6 5 6 0 0 7 7 3 2 13 5 12 1 5 18 9 5 18 0 18 9 10 19 1 14 15 12 7 7 6 3 8 5 2 17 3 10 6 2 2 12 1 17 19 9 6 7 3 10 18 5 12 5 10 11 2 8 3 19 6 15 19 13 17 6 9 5 1 1 2 10 7 17 4 18 14 7 18 12 0 12 13 17 14 12 12 13 11 0 2 18 9 8 6 3 16 5 9 10 0 13 0 10 6 5 17 0 4 8 3 6 18 14 15 5 ...
output:
1
result:
ok single line: '1'
Test #34:
score: 40
Accepted
time: 3ms
memory: 10744kb
input:
1400 10 0 1 1 1 3 3 1 0 7 1 5 3 8 0 6 11 6 13 4 5 5 17 4 6 13 21 3 24 19 21 21 13 0 29 5 2 29 23 15 4 14 24 33 15 44 4 5 13 7 10 46 24 25 15 48 43 16 0 57 35 43 35 33 50 20 46 21 4 6 1 1 42 8 44 8 17 30 70 40 0 8 3 80 10 14 26 66 2 45 1 46 73 0 8 89 25 4 60 51 26 61 50 85 29 38 17 84 88 30 44 1 64 1...
output:
5
result:
ok single line: '5'
Test #35:
score: 40
Accepted
time: 0ms
memory: 10664kb
input:
1400 12 0 0 0 1 0 1 3 2 1 1 4 7 5 0 7 9 13 8 2 18 5 2 14 18 11 12 5 0 9 27 5 1 9 21 4 10 21 25 15 26 23 8 36 15 37 0 1 38 27 49 26 9 20 45 6 48 36 24 34 16 34 11 36 57 28 21 11 53 32 53 44 22 17 24 52 28 9 36 64 71 20 74 23 15 45 0 31 87 43 22 88 21 67 31 12 18 73 67 30 8 7 74 60 85 18 94 16 20 15 6...
output:
5
result:
ok single line: '5'
Test #36:
score: 40
Accepted
time: 3ms
memory: 10736kb
input:
1500 10 0 1 0 2 3 4 5 5 6 1 10 4 6 11 12 7 11 6 7 1 19 14 20 12 21 12 6 1 18 9 16 16 25 19 18 21 22 4 18 24 25 7 14 8 31 12 29 46 40 5 43 4 7 52 12 17 11 42 43 32 9 48 24 17 24 63 8 10 48 1 9 33 28 25 64 20 71 49 69 5 26 1 73 19 42 78 24 84 9 21 39 65 80 12 80 57 50 36 68 92 97 57 46 7 88 72 21 50 5...
output:
7
result:
ok single line: '7'
Test #37:
score: 40
Accepted
time: 0ms
memory: 10680kb
input:
1500 4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 79 93 ...
output:
50
result:
ok single line: '50'
Test #38:
score: 40
Accepted
time: 0ms
memory: 10900kb
input:
1500 50 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...
output:
7
result:
ok single line: '7'
Test #39:
score: 40
Accepted
time: 3ms
memory: 10828kb
input:
1500 70 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...
output:
8
result:
ok single line: '8'
Test #40:
score: 40
Accepted
time: 0ms
memory: 10776kb
input:
1500 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100...
output:
301
result:
ok single line: '301'
Subtask #3:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Test #41:
score: 0
Time Limit Exceeded
input:
190001 5 0 1 2 0 4 5 0 7 8 0 10 11 0 13 14 0 16 17 0 19 20 0 22 23 0 25 26 0 28 29 0 31 32 0 34 35 0 37 38 0 40 41 0 43 44 0 46 47 0 49 50 0 52 53 0 55 56 0 58 59 0 61 62 0 64 65 0 67 68 0 70 71 0 73 74 0 76 77 0 79 80 0 82 83 0 85 86 0 88 89 0 91 92 0 94 95 0 97 98 0 100 101 0 103 104 0 106 107 0 1...