QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#789569 | #9751. 覆盖一棵树 | sunup15# | WA | 25ms | 27184kb | C++20 | 822b | 2024-11-27 20:53:42 | 2024-11-27 20:53:42 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10,INF=1e9;
vector<int>e[N];
int depth[N];
int d[N];
int n;
int mx;
void dfs(int u)
{
vector<int>a;
for(int v:e[u])
{
dfs(v);
depth[u]=min(depth[u],depth[v]+1);
a.push_back(depth[v]+1);
}
sort(a.begin(),a.end());
mx=max(mx,depth[u]);
if(a.size()>1)mx=max(mx,a[1]);
}
void solve()
{
cin>>n;
mx=0;
for(int i=1;i<=n;i++)
{
e[i].clear();
depth[i]=INF;
d[i]=0;
}
for(int i=2;i<=n;i++)
{
int x;
cin>>x;
d[i]++;
d[x]++;
e[x].push_back(i);
}
for(int i=2;i<=n;i++)
{
if(d[i]==1)depth[i]=0;
}
dfs(1);
cout<<mx<<'\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5912kb
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: 5616kb
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: 13ms
memory: 3644kb
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: 15ms
memory: 3712kb
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: 17ms
memory: 7080kb
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: 25ms
memory: 17880kb
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: 17ms
memory: 26732kb
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: 20ms
memory: 27184kb
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: -100
Wrong Answer
time: 22ms
memory: 15176kb
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:
7
result:
wrong answer 1st lines differ - expected: '8', found: '7'