QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #743562 | #9751. 覆盖一棵树 | huaxiamengjin | AC ✓ | 60ms | 14096kb | C++14 | 481b | 2024-11-13 19:30:12 | 2024-11-13 19:30:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,fa[1001001],f[1001001],h[1001001];
void solve(){
cin>>n;
for (int i=2;i<=n;i++)
cin>>fa[i];
for (int i=1;i<=n;i++)
f[i]=1e9,h[i]=0;
int ans=0;
for (int i=n;i;i--){
if(f[i]==1e9)f[i]=0;
f[fa[i]]=min(f[fa[i]],f[i]+1);
h[fa[i]]=max(h[fa[i]],f[i]+1);
ans=max(ans,h[i]);
}
cout<<ans<<"\n";
}
int main(){
int T;cin>>T;
while(T--)solve();
}
这程序好像有点Bug，我给组数据试试？
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7668kb
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: 23ms
memory: 7724kb
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: 26ms
memory: 7704kb
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: 25ms
memory: 7804kb
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: 29ms
memory: 7764kb
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: 30ms
memory: 10100kb
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: 36ms
memory: 13948kb
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: 31ms
memory: 12380kb
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: 38ms
memory: 12352kb
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: 37ms
memory: 12596kb
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: 33ms
memory: 8564kb
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: 33ms
memory: 12380kb
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: 30ms
memory: 14096kb
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: 30ms
memory: 10112kb
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: 60ms
memory: 7664kb
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: 18ms
memory: 8436kb
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: 37ms
memory: 8512kb
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