QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#784981 | #9751. 覆盖一棵树 | ChuanhuaYu# | AC ✓ | 16ms | 20008kb | C++17 | 1.1kb | 2024-11-26 16:30:01 | 2024-11-26 16:30:02 |
Judging History
answer
// Author: Chuanhua Yu
// Time: 2024-11-26.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;
int n, tot;
int head[N], ver[N], nxt[N], h[N], th[N];
void add(int x, int y){
ver[++tot] = y; nxt[tot] = head[x]; head[x] = tot;
}
void dfs(int x){
for(int i = head[x]; i; i = nxt[i]){
int y = ver[i];
dfs(y);
if(th[x]) th[x] = min(th[x], th[y] + 1);
else th[x] = th[y] + 1;
}
for(int i = head[x]; i; i = nxt[i])
h[x] = max(h[x], th[ver[i]] + 1);
}
void solve(){
tot = 1;
cin >> n;
memset(head, 0, (n + 1) * sizeof(int));
memset(h, 0, (n + 1) * sizeof(int));
memset(th, 0, (n + 1) * sizeof(int));
for(int i = 2; i <= n; i++){
int p; cin >> p;
add(p, i);
}
dfs(1);
int ans = 0;
for(int i = 1; i <= n; i++) ans = max(ans, h[i]);
cout << ans << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int T; cin >> T;
while(T--)
solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5564kb
input:
2 8 1 2 3 2 5 1 7 8 1 2 3 4 5 6 7
output:
3 7
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 9ms
memory: 5768kb
input:
33428 10 1 2 3 3 4 6 7 7 9 10 1 2 3 4 5 6 7 8 8 8 1 2 3 4 5 6 7 8 1 2 3 4 4 6 7 4 1 2 3 3 1 2 3 1 1 9 1 2 3 4 5 6 7 8 2 1 3 1 2 10 1 2 3 4 5 6 7 8 9 3 1 2 2 1 10 1 2 3 4 5 6 7 8 9 2 1 5 1 2 2 4 8 1 2 3 4 5 6 7 5 1 2 3 3 2 1 5 1 2 3 4 3 1 2 9 1 2 3 4 5 6 6 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 5 7 8 8 1 2 ...
output:
4 8 7 4 3 2 1 8 1 2 9 2 1 9 1 2 7 3 1 4 2 6 8 5 6 4 1 2 9 7 4 3 4 5 7 3 3 7 3 4 9 3 3 3 8 2 8 6 2 4 6 4 2 1 5 2 5 2 2 4 2 2 5 2 2 6 3 9 2 5 5 3 2 2 1 2 1 9 1 5 1 6 3 5 2 9 4 2 3 1 3 3 1 2 5 3 8 4 7 6 4 6 4 6 8 4 4 2 4 5 1 7 7 5 2 2 2 2 7 3 3 6 4 3 3 3 2 2 4 8 4 5 8 6 4 2 3 7 6 1 3 2 7 7 9 1 2 5 5 2 ...
result:
ok 33428 lines
Test #3:
score: 0
Accepted
time: 9ms
memory: 5680kb
input:
3934 19 1 2 3 3 4 6 7 7 9 10 11 12 13 14 15 16 17 18 65 1 2 3 4 5 5 7 8 9 10 11 12 12 14 15 16 17 18 19 19 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 39 41 42 43 44 44 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 60 62 63 63 66 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 19 21 22 2...
output:
11 20 24 28 10 23 5 31 8 19 7 14 1 15 14 14 15 9 11 10 11 13 5 31 23 9 11 23 32 18 17 18 10 14 1 24 1 28 18 13 9 10 9 12 24 5 27 27 9 29 15 17 23 20 17 11 14 12 19 9 19 13 17 16 14 7 17 23 5 20 11 14 8 9 18 2 9 16 29 17 2 31 13 14 3 16 9 26 14 15 13 5 17 18 19 24 12 20 10 10 13 14 13 2 12 10 15 18 1...
result:
ok 3934 lines
Test #4:
score: 0
Accepted
time: 10ms
memory: 5800kb
input:
386 208 1 2 3 3 4 6 7 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 31 33 34 35 36 37 38 38 40 41 41 43 43 45 46 47 48 49 50 51 51 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 69 70 72 73 74 75 75 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:
27 31 36 29 27 27 23 31 27 30 25 28 37 14 27 23 35 30 32 52 38 58 31 34 28 43 37 39 32 33 22 34 28 27 39 25 25 45 32 23 25 47 24 48 28 34 45 22 26 37 13 32 32 24 40 22 26 33 23 25 31 21 19 45 9 24 23 27 27 32 40 15 22 33 21 44 36 29 24 28 44 43 23 43 31 19 36 33 50 22 18 20 9 41 34 58 22 25 21 18 34...
result:
ok 386 lines
Test #5:
score: 0
Accepted
time: 11ms
memory: 6268kb
input:
42 8830 1 2 3 3 4 6 7 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 31 33 34 35 36 37 38 38 40 41 41 43 43 45 46 47 48 49 50 51 51 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 69 70 72 73 74 75 75 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:
65 52 46 34 42 48 35 40 40 43 42 46 44 44 52 39 54 37 43 29 40 38 45 43 51 48 35 37 56 48 47 37 30 42 42 32 43 56 53 53 48 37
result:
ok 42 lines
Test #6:
score: 0
Accepted
time: 9ms
memory: 11600kb
input:
5 51400 1 2 3 3 4 6 7 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 31 33 34 35 36 37 38 38 40 41 41 43 43 45 46 47 48 49 50 51 51 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 69 70 72 73 74 75 75 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:
65 58 58 37 57
result:
ok 5 lines
Test #7:
score: 0
Accepted
time: 11ms
memory: 15368kb
input:
2 56002 1 2 3 3 4 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 31 33 34 35 36 37 38 38 40 41 41 43 43 45 46 47 48 49 50 51 51 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 70 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:
119 105
result:
ok 2 lines
Test #8:
score: 0
Accepted
time: 16ms
memory: 15592kb
input:
2 56002 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:
56001 143997
result:
ok 2 lines
Test #9:
score: 0
Accepted
time: 9ms
memory: 7540kb
input:
1 200000 1 2 2 4 4 6 7 8 8 8 11 12 8 7 7 7 17 6 19 19 6 4 4 24 25 25 27 27 29 24 31 31 31 34 4 36 36 2 39 40 39 39 43 44 45 46 47 48 47 47 51 52 45 54 45 56 57 56 59 45 61 62 61 64 64 66 45 68 69 69 71 71 73 73 69 76 77 78 78 68 68 82 68 45 85 85 87 85 89 90 91 91 90 94 94 90 89 98 98 100 101 102 98...
output:
8
result:
ok single line: '8'
Test #10:
score: 0
Accepted
time: 11ms
memory: 7512kb
input:
1 200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39 39...
output:
2
result:
ok single line: '2'
Test #11:
score: 0
Accepted
time: 13ms
memory: 8024kb
input:
1 200000 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:
247
result:
ok single line: '247'
Test #12:
score: 0
Accepted
time: 11ms
memory: 7588kb
input:
1 200000 1 1 1 1 1 1 1 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 1 1 1 133 133 133 133 133 133 133...
output:
2
result:
ok single line: '2'
Test #13:
score: 0
Accepted
time: 8ms
memory: 7732kb
input:
1 200000 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:
161
result:
ok single line: '161'
Test #14:
score: 0
Accepted
time: 12ms
memory: 6488kb
input:
2 100000 1 2 3 4 3 6 3 3 9 3 11 12 13 3 15 15 15 2 19 2 2 2 1 24 25 26 27 28 29 30 30 29 27 27 35 36 37 38 27 27 41 42 42 26 45 46 47 47 49 50 51 46 53 53 46 56 46 58 58 60 61 61 63 60 65 65 60 68 58 70 70 72 70 74 74 76 74 78 79 79 78 82 78 84 78 74 87 88 89 90 74 74 93 58 46 96 97 98 98 98 101 102...
output:
7 7
result:
ok 2 lines
Test #15:
score: 0
Accepted
time: 10ms
memory: 3660kb
input:
100000 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 100000 lines
Test #16:
score: 0
Accepted
time: 8ms
memory: 7464kb
input:
1 200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
1
result:
ok single line: '1'
Test #17:
score: 0
Accepted
time: 13ms
memory: 20008kb
input:
1 200000 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:
199999
result:
ok single line: '199999'
Extra Test:
score: 0
Extra Test Passed