QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#202371 | #6638. Treelection | ucup-team870 | WA | 566ms | 62424kb | C++20 | 1.3kb | 2023-10-05 23:41:32 | 2023-10-05 23:41:32 |
Judging History
answer
//dp_i: i的子树中必须往i祖先上贡献的. (不包含i!!!!!!!!!)
#include<bits/stdc++.h>
using namespace std;
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define P pair<int,int>
#define ll long long
#define vi vector<int>
const int N=1e6+6;
int fa[N],res[N],dp[N],V,sz[N],ok[N];
vi tu[N];
void dfs(int now){
int sum=0; sz[now]=1;
for(int son:tu[now]){
dfs(son); sum+=dp[son]+1; sz[now]+=sz[son];
}
dp[now]=max(0,sum-V);
}
void slv(){
int n; cin>>n;
rep(i,1,n){
tu[i].clear(); res[i]=0;
}
rep(i,2,n){
cin>>fa[i];
tu[fa[i]].push_back(i);
}
int L=1,R=n-1;
while(L<=R){
V=L+R>>1; dfs(1);
if(dp[1])L=V+1;
else R=V-1;
}
V=L-1; dfs(1); assert(dp[1]);
V=L;
ok[1]=(dp[1]==1);
rep(i,2,n){
ok[i]=(dp[i]==1 && ok[fa[i]]);
}
rep(i,1,n){
int v=sz[i]-1;
if(v>V)res[i]=1;
else if(v<V)res[i]=0;
else{
if(ok[i])res[i]=1;
else res[i]=0;
}
}
rep(i,1,n)cout<<res[i]; cout<<'\n';
}
signed main(){
IOS
int T;cin>>T;
while(T--)slv();
}
/*
1
100000
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 35744kb
input:
2 4 1 2 3 5 1 1 2 2
output:
1100 10000
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 130ms
memory: 37600kb
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: 166ms
memory: 62424kb
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: 566ms
memory: 56980kb
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: -100
Wrong Answer
time: 144ms
memory: 38124kb
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:
wrong answer 187th lines differ - expected: '11111000000000', found: '11101000000000'