QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#210820 | #6638. Treelection | yz_ly | WA | 59ms | 12712kb | C++14 | 1.9kb | 2023-10-11 20:25:41 | 2023-10-11 20:25:42 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
inline int read(){
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-f;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
inline void work(int k){
if(k<0){
putchar('-');
k=-k;
}
if(k>9)
work(k/10);
putchar(k%10+'0');
}
//考虑二分最小的k,可以使得所有点的得票数<=k
//check函数就是尽可能让这个点得票更多就行,实在不行,往上送票
//这个时候,如果siz[u]-1>k则它可以成为票数最多的人,siz[u]-1<k则一定不可以
//我们只需要看siz[u]-1==k的合不合法即可
//我们这时候跑一遍check(k-1),因为这个时候除根节点外,其它点的票数都是<=k-1的
//如果根节点的得票数为k,那么siz[u]-1==k的点无论哪一个都可以把这一票拿回去成为票数最多的点
//否则这些点必须有两个点拿回去才行,所以这些点都不能成为票数最多的点
int t,n,cnt,first[1000005],s[1000005],dp[1000005];
struct node{
int u,w,nex;
}a[1000005];
void add(int u1,int w1){
a[++cnt]={u1,w1,first[u1]};
first[u1]=cnt;
}
void init(int u){
s[u]=1;
for(int i=first[u];i;i=a[i].nex){
init(a[i].w);
s[u]+=s[a[i].w];
}
}
int dfs(int u,int k){
dp[u]=0;
for(int i=first[u];i;i=a[i].nex){
dp[u]+=dfs(a[i].w,k);
}
return max(dp[u]-k,0)+1;
}
bool check(int mid){
dfs(1,mid);
return dp[1]<=mid;
}
int main(){
t=read();
while(t--){
n=read();
cnt=0;
for(int i=1;i<=n;i++){
first[i]=0;
}
for(int i=1,x;i<n;i++){
x=read();
add(x,i+1);
}
init(1);
int l=1,r=n;
while(l<r){
int mid=(l+r)>>1;
if(check(mid))
r=mid;
else
l=mid+1;
}
dfs(1,l-1);
for(int i=1;i<=n;i++){
if(s[i]-1>l)
work(1);
else if(s[i]-1==l){
if(dp[1]==l)
work(1);
else
work(0);
}
else
work(0);
}
putchar('\n');
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 9736kb
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: 59ms
memory: 12712kb
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'