QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #210672 | #6638. Treelection | zyxawa | WA | 137ms | 19596kb | C++14 | 739b | 2023-10-11 18:37:59 | 2023-10-11 18:37:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int t,n,dp[1000001],siz[1000001],vis[1000001],fa[1000001];
bool solve(int mid){
for(int i=1;i<=n;i++) dp[i]=0;
for(int i=n;i>=1;i--) dp[i]=max(0,dp[i]-mid),dp[fa[i]]+=dp[i]+1;
return !dp[1];
}
int main(){
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=2;i<=n;i++) scanf("%d",&fa[i]),siz[i]=1,vis[i]=0;
for(int i=n;i>=2;i--) siz[fa[i]]+=siz[i];
int l=1,r=n;
while(l<r){
int mid=(l+r)>>1;
if(!solve(mid)) l=mid+1;
else r=mid;
}
solve(l-1);
if(dp[1]==1){
vis[1]=1;
for(int i=2;i<=n;i++) vis[i]=vis[fa[i]]&(dp[i]>0);
}
for(int i=1;i<=n;i++) printf("%d",(siz[i]-1>l)|(vis[i]&(siz[i]-1==l)));
printf("\n");
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 10060kb
input:
2 4 1 2 3 5 1 1 2 2
output:
1100 10000
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 107ms
memory: 14560kb
input:
10 100000 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:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok 10 lines
Test #3:
score: 0
Accepted
time: 106ms
memory: 19556kb
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:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok single line: '111111111111111111111111111111...0000000000000000000000000000000'
Test #4:
score: 0
Accepted
time: 103ms
memory: 19540kb
input:
1 1000000 1 2 2 3 5 1 7 3 9 8 4 11 9 6 10 12 10 13 16 18 14 16 7 24 23 21 14 8 26 27 17 21 33 24 20 17 5 34 29 34 37 20 12 22 39 44 33 37 32 27 31 25 30 46 39 26 53 4 11 55 41 29 6 22 32 36 52 57 65 38 59 67 51 56 30 61 36 64 62 19 51 63 53 83 38 75 31 41 49 43 60 18 62 67 91 81 44 25 55 98 86 64 46...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok single line: '111111111111111111111111111111...0000000000000000000000000000000'
Test #5:
score: 0
Accepted
time: 91ms
memory: 10444kb
input:
65764 13 1 1 1 1 1 1 1 1 2 10 10 11 11 1 1 2 2 2 4 4 4 5 10 14 1 2 2 3 3 3 4 4 5 6 10 12 13 14 1 2 2 3 3 3 4 5 5 6 6 7 8 13 1 2 2 3 3 4 5 5 5 6 8 12 13 1 1 1 2 2 3 5 7 7 7 9 9 12 1 1 1 2 2 3 5 7 7 9 10 14 1 1 2 2 3 4 5 6 7 7 8 12 12 14 1 2 3 4 4 5 5 5 7 7 7 10 13 14 1 1 1 1 1 2 2 2 3 10 10 10 11 13 ...
output:
1000000000000 11000000000 11101000010000 11100000000000 1110100000000 1010001000000 101000100000 11011001000000 11111010000000 10000000000000 1111010000000 111000100010000 111010001000 11000000000000 11100000000000 11001001000000 11000000000000 11111000000000 110011000000 1010000100000 1100111010000...
result:
ok 65764 lines
Test #6:
score: 0
Accepted
time: 108ms
memory: 19476kb
input:
1 1000000 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52...
output:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok single line: '111111111111111111111111111111...0000000000000000000000000000000'
Test #7:
score: 0
Accepted
time: 137ms
memory: 19596kb
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:
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...
result:
ok single line: '111111111111111111111111111111...1111111111111111111111111111100'
Test #8:
score: -100
Wrong Answer
time: 125ms
memory: 19528kb
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:
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
wrong answer 1st lines differ - expected: '100000000000000000000000000000...0000000000000000000000000000000', found: '000000000000000000000000000000...0000000000000000000000000000000'