QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#208803 | #6638. Treelection | czc | TL | 2055ms | 37776kb | C++14 | 1.5kb | 2023-10-09 21:02:15 | 2023-10-09 21:02:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
vector<int> G[maxn];
int n,siz[maxn],rest[maxn],val[maxn];
inline void dfs(int x){
siz[x]=1;
for(auto v:G[x]){
dfs(v);
siz[x]+=siz[v];
}
}
inline void dfs2(int x,int mid){
rest[x]=0;
for(auto v:G[x]){
dfs2(v,mid);
rest[x]+=rest[v];
}
if(x!=1){
val[x]=min(rest[x],mid);
rest[x]-=val[x];
rest[x]++;
}
}
inline bool check(int mid){
dfs2(1,mid);
return rest[1]<=mid;
}
int vis[maxn],fa[maxn];
vector<int> V;
inline void solve(){
cin>>n;
for(int i=1,x;i<=n;i++){
vis[i]=0;
G[i].clear();
if(i!=1){
cin>>x;
G[x].push_back(i);
fa[i]=x;
}
}
dfs(1);
int l=0,r=n;
// cout<<check(1)<<endl;
// for(int i=1;i<=n;i++){
// cout<<rest[i]<<" ";
// }
// cout<<endl;
// for(int i=1;i<=n;i++){
// cout<<val[i]<<" ";
// }
// cout<<endl;
// for(int i=1;i<=n;i++){
// cout<<siz[i]<<" ";
// }
// cout<<endl;
while(l<r){
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
// cout<<l<<endl;
V.clear();
for(int i=1;i<=n;i++){
if(siz[i]-1>l) vis[i]=1;
if(siz[i]-1==l) V.push_back(i);
}
dfs2(1,l-1);
for(auto x:V){
bool f=0;
for(int y=x;y!=1;y=fa[y]){
if(rest[y]<2) f=1;
}
if(!f && rest[1]-1<siz[x]-1){
vis[x]=1;
}
}
for(int i=1;i<=n;i++){
putchar(vis[i]+'0');
}
puts("");
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int T;
cin>>T;
while(T--){
solve();
}
return 0;
}
/*
a a a a
b
ans ans ans
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 35960kb
input:
2 4 1 2 3 5 1 1 2 2
output:
1100 10000
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 2055ms
memory: 37776kb
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: -100
Time Limit Exceeded
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...