QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#830025 | #9751. 覆盖一棵树 | wiki | AC ✓ | 13ms | 24016kb | C++14 | 852b | 2024-12-24 15:30:39 | 2024-12-24 15:30:40 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+20;
int t,n,ans,dp[N];
vector<int> g[N];
bool vis[N];
inline int read()
{
int k=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){k=(k<<1)+(k<<3)+ch-'0';ch=getchar();}
return k*f;
}
int dfs(int fx)
{
int len=n+1;
for(int i=0;i<g[fx].size();i++)
{
int k=g[fx][i];
int d=dfs(k);
ans=max(ans,d+1);
len=min(len,d+1);
}
if(len==n+1) len=0;//叶子节点
return len;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
t=read();
while(t--)
{
n=read();
for(int i=1;i<=n;i++) g[i].clear();
for(int i=2,fa;i<=n;i++)
{
fa=read();
g[fa].push_back(i);
}
ans=0;
int cmp=dfs(1);
ans=max(ans,cmp);
cout<<ans<<'\n';
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 8384kb
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: 6ms
memory: 8424kb
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: 7ms
memory: 8908kb
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: 7ms
memory: 8452kb
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: 8ms
memory: 9808kb
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: 13ms
memory: 14932kb
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: 18884kb
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: 7ms
memory: 19656kb
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: 11ms
memory: 11652kb
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: 3ms
memory: 9380kb
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: 12ms
memory: 12588kb
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: 7ms
memory: 9480kb
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: 13ms
memory: 12384kb
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: 7ms
memory: 11488kb
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: 7ms
memory: 8272kb
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: 5ms
memory: 9596kb
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: 3ms
memory: 24016kb
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