QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#201568 | #6638. Treelection | ucup-team870 | WA | 138ms | 37360kb | C++17 | 1.1kb | 2023-10-05 15:11:13 | 2023-10-05 15:11:13 |
Judging History
answer
#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 res[N],dp[N],V,sz[N];
vi tu[N];
void dfs(int now){
int sum=0; sz[now]=1;
for(int son:tu[now]){
dfs(son); sum+=dp[son]; sz[now]+=sz[son];
}
dp[now]=(now!=1)+max(0,sum-V);
}
void slv(){
int n; cin>>n;
rep(i,1,n){
tu[i].clear(); res[i]=0;
}
rep(i,2,n){
int p;cin>>p; tu[p].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);
V=L;
// cout<<V<<':';
rep(i,1,n){
int v=sz[i]-1;
// cout<<v<<' ';
if(v>V)res[i]=1;
else if(v<V)res[i]=0;
else{
if(dp[1]==1 && dp[i]==1)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();
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 31556kb
input:
2 4 1 2 3 5 1 1 2 2
output:
1100 10000
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 138ms
memory: 37360kb
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:
wrong answer 1st lines differ - expected: '111111111111111111111111111111...0000000000000000000000000000000', found: '111111111111111111111111111111...0000000000000000000000000000000'