QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#632385 | #5124. Tree | Green_Hand# | AC ✓ | 21ms | 17152kb | C++20 | 1023b | 2024-10-12 13:18:35 | 2024-10-12 13:18:40 |
Judging History
answer
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1E6 + 7;
int n,l,r,ans,now,T,id[N],q[N],D[N],fa[N];
int min(int x,int y) { return x < y ? x : y; }
int max(int x,int y) { return x > y ? x : y; }
void read(int &x)
{
char c = getchar(); x = 0;
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}
int main()
{
for(read(T);T--;)
{
read(n);
for(int i = 1;i <= n; ++ i) D[i] = 0;
for(int i = 2;i <= n; ++ i) read(fa[i]), ++D[fa[i]];
now = l = 1, r = 0;
for(int i = 1;i <= n; ++ i)
!D[i] && (q[++r] = i, id[i] = 1) || (now += D[i] - 1);
ans = now;
for(int i = 1;l <= r; ++ i)
{
for(int x;l <= r && id[x = q[l]] == i; ++ l)
{
now -= max(0,D[fa[x]] - 1);
if(x == 1) { ans = min(ans,i); continue; }
if(!--D[fa[x]]) id[fa[x]] = i + 1, q[++r] = fa[x];
else now += D[fa[x]] - 1;
}
ans = min(ans,now + i);
}
printf("%d\n",ans);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 7644kb
input:
2 7 1 1 2 2 2 3 5 1 2 3 4
output:
3 1
result:
ok 2 number(s): "3 1"
Test #2:
score: 0
Accepted
time: 8ms
memory: 7616kb
input:
46234 1 2 1 3 1 1 4 1 1 1 5 1 1 1 1 6 1 1 1 1 1 7 1 1 1 1 1 1 8 1 1 1 1 1 1 1 9 1 1 1 1 1 1 1 1 9 1 1 1 1 1 1 1 2 9 1 1 1 1 1 1 1 3 9 1 1 1 1 1 1 1 4 9 1 1 1 1 1 1 1 5 9 1 1 1 1 1 1 1 6 9 1 1 1 1 1 1 1 7 9 1 1 1 1 1 1 1 8 8 1 1 1 1 1 1 2 9 1 1 1 1 1 1 2 1 9 1 1 1 1 1 1 2 2 9 1 1 1 1 1 1 2 3 9 1 1 1...
output:
1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 2 2 2 3 2 3 3 3 3 2 2 2 3 3 2 3 3 3 2 2 2 3 3 3 2 3 3 2 2 2 3 3 3 3 2 3 2 2 2 3 3 3 3 3 2 2 2 2 2 2 3 3 3 3 2 3 2 2 2 3 3 3 3 2 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 2 2 3 3 3 3 2 2 2 2 2 3 2 3 3 3 2 3 3 3 3 3 3 3 ...
result:
ok 46234 numbers
Test #3:
score: 0
Accepted
time: 19ms
memory: 17096kb
input:
1 1000000 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:
1
result:
ok 1 number(s): "1"
Test #4:
score: 0
Accepted
time: 13ms
memory: 17140kb
input:
1 1000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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:
2
result:
ok 1 number(s): "2"
Test #5:
score: 0
Accepted
time: 16ms
memory: 17104kb
input:
1 1000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 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:
1000
result:
ok 1 number(s): "1000"
Test #6:
score: 0
Accepted
time: 20ms
memory: 17136kb
input:
1 1000000 1 1 1 2 3 4 5 6 7 3 6 8 9 10 13 11 12 13 14 15 8 16 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 51 39 54 55 56 57 58 59 60 61 68 62 63 64 65 66 67 68 69 70 71 59 72 73 74 75 76 77 78 79 80 81 82 32 23 83 84 85 86 87 88 8...
output:
1405
result:
ok 1 number(s): "1405"
Test #7:
score: 0
Accepted
time: 21ms
memory: 17120kb
input:
1 1000000 1 1 1 1 2 3 4 5 6 7 8 9 10 11 14 1 12 13 14 15 19 16 17 18 19 20 21 20 22 23 24 25 26 27 28 20 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 29 46 47 48 49 50 51 52 53 54 53 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 51 76 77 78 79 80 81 82 83 84 85 86 23 87 88 89 ...
output:
1404
result:
ok 1 number(s): "1404"
Test #8:
score: 0
Accepted
time: 18ms
memory: 17152kb
input:
1 1000000 1 1 1 2 4 3 4 5 6 7 8 9 10 5 10 11 12 13 11 17 14 15 16 17 18 19 20 21 22 23 24 25 26 27 14 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 16 45 46 47 48 49 50 51 52 53 17 54 55 56 57 58 59 60 61 62 63 40 67 64 65 66 67 68 69 70 71 72 73 74 54 35 75 76 77 78 79 80 81 82 83 84 85 86 87 ...
output:
1406
result:
ok 1 number(s): "1406"
Test #9:
score: 0
Accepted
time: 17ms
memory: 8232kb
input:
7 142857 1 1 2 1 2 3 4 4 8 5 6 7 8 9 10 11 12 13 14 7 15 15 16 17 18 19 20 21 22 23 24 25 26 27 28 17 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 14 55 56 57 58 59 60 61 62 63 27 69 43 64 65 66 67 68 69 70 71 72 73 57 15 74 75 76 77 78 79 80 81 82 83 84 85 86 36 87 ...
output:
528 527 526 527 527 527 527
result:
ok 7 numbers
Test #10:
score: 0
Accepted
time: 21ms
memory: 8000kb
input:
10 100000 1 1 2 2 2 3 4 5 6 7 8 6 8 9 10 11 12 13 14 15 16 17 22 18 19 20 21 22 23 8 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 27 39 40 41 42 43 44 45 46 39 39 48 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 59 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89...
output:
439 439 441 439 441 441 442 441 441 440
result:
ok 10 numbers
Test #11:
score: 0
Accepted
time: 21ms
memory: 9932kb
input:
15 66666 1 2 3 1 2 3 4 5 6 1 7 8 9 10 2 11 12 13 14 15 16 17 18 19 20 21 19 22 23 24 25 26 27 34 28 29 30 31 32 33 34 10 35 36 37 38 39 40 41 42 22 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 57 20 62 63 64 65 66 67 68 69 70 71 77 72 73 74 75 76 77 78 79 80 81 82 83 77 84 85 86 87 88 89...
output:
360 358 359 359 359 359 359 360 359 360 359 361 358 360 359
result:
ok 15 numbers
Test #12:
score: 0
Accepted
time: 11ms
memory: 9780kb
input:
57 17543 1 1 2 2 3 5 4 5 6 3 7 8 9 10 3 1 4 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 25 32 33 34 35 36 37 38 39 3 40 41 42 43 44 45 46 47 48 6 49 50 51 52 53 54 55 56 57 58 26 59 60 61 62 63 64 65 66 67 68 69 69 17 70 71 72 73 74 75 76 77 78 79 80 81 54 82 83 84 85 86 87 88 89 ...
output:
181 182 181 182 182 183 183 183 182 183 183 182 181 184 183 183 182 181 181 183 182 183 181 183 182 182 182 183 183 183 180 182 183 183 182 181 181 181 183 183 182 182 180 182 181 183 182 182 183 183 183 181 180 181 181 182 183
result:
ok 57 numbers
Test #13:
score: 0
Accepted
time: 18ms
memory: 7600kb
input:
100 10000 1 2 2 2 3 5 3 4 5 6 7 8 9 10 11 12 13 14 15 9 8 16 17 18 19 20 2 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 11 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 3 49 19 21 13 61 62 63 64 65 66 67 68 69 20 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 8...
output:
136 138 138 136 135 137 136 136 137 138 137 137 138 138 138 137 137 137 138 137 137 136 138 136 138 138 138 137 137 138 137 136 136 137 137 137 137 138 137 136 137 138 136 136 138 138 136 137 137 138 136 137 137 138 137 138 137 138 136 135 138 137 136 137 134 137 137 136 137 137 135 136 138 138 136 ...
result:
ok 100 numbers
Test #14:
score: 0
Accepted
time: 12ms
memory: 7680kb
input:
1000 1000 1 1 2 3 5 4 5 5 9 6 7 8 9 10 11 12 13 17 9 14 15 16 17 18 1 19 20 21 22 23 24 25 3 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 30 43 44 45 46 47 48 49 50 51 8 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 70 71 50 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 9...
output:
43 42 42 42 41 41 42 41 42 42 41 42 42 42 42 41 42 41 42 42 42 41 42 41 42 42 42 40 43 40 42 42 40 42 42 42 41 41 42 41 41 41 42 42 42 41 42 41 42 42 42 42 42 42 41 42 43 41 40 41 42 42 42 43 42 40 41 42 42 41 41 41 42 42 43 41 41 41 42 40 42 42 42 42 41 42 42 42 42 43 41 41 42 41 41 41 42 42 42 42 ...
result:
ok 1000 numbers
Test #15:
score: 0
Accepted
time: 11ms
memory: 7648kb
input:
10000 100 1 1 3 2 2 3 4 5 7 6 7 8 9 10 11 12 13 14 4 2 10 15 16 17 18 19 5 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 23 46 47 48 49 50 51 52 53 54 16 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 13 37 49 76 77 78 79 80 81 82 83 84 85 86 100 1 2 2...
output:
12 12 13 12 12 12 12 11 12 12 12 12 13 13 12 12 12 11 13 13 12 12 13 12 12 12 12 13 13 13 12 12 12 13 11 13 13 12 12 12 13 12 12 12 12 12 12 12 12 11 12 13 11 13 12 12 12 12 12 12 12 13 12 12 12 11 12 12 13 13 12 13 12 13 12 11 12 11 11 12 13 12 13 12 12 13 12 12 12 12 12 12 12 12 12 12 12 11 12 13 ...
result:
ok 10000 numbers
Test #16:
score: 0
Accepted
time: 14ms
memory: 7668kb
input:
100000 10 1 2 1 2 3 4 5 6 7 10 1 1 1 2 3 6 4 5 6 10 1 1 3 2 3 1 4 5 6 10 1 2 1 2 3 4 5 6 7 10 1 2 3 1 2 3 4 5 6 10 1 2 1 2 3 4 5 6 7 10 1 1 2 4 3 4 5 6 7 10 1 1 1 2 3 4 5 6 7 10 1 2 2 4 3 3 4 5 6 10 1 2 1 2 3 4 5 6 7 10 1 1 3 2 3 6 4 5 6 10 1 2 2 4 3 2 4 5 6 10 1 1 1 2 3 5 4 5 6 10 1 2 2 4 3 4 5 6 7...
output:
3 4 4 3 3 3 3 3 3 3 4 3 4 3 4 4 3 3 3 3 3 4 4 4 4 3 3 3 3 3 4 4 4 4 3 3 3 3 3 4 3 4 4 3 3 4 3 3 4 3 4 3 3 3 3 3 4 3 3 3 3 4 3 3 3 3 3 4 3 3 4 3 4 4 3 3 4 3 3 4 3 3 3 4 4 3 3 3 3 3 4 3 4 4 3 3 3 3 4 3 4 3 3 4 3 3 4 3 4 4 3 3 4 4 4 3 3 3 3 3 4 3 3 3 4 3 4 3 3 3 3 4 3 4 3 4 3 4 3 4 3 3 3 4 4 3 4 4 3 3 ...
result:
ok 100000 numbers