QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#207119 | #6638. Treelection | sumi007 | WA | 278ms | 67292kb | C++14 | 2.0kb | 2023-10-08 09:39:41 | 2023-10-08 09:39:42 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define i64 __int128
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(i) i&(-i)
const int N = 1e6+7;
int n,d[N],f[N],p[N],cnt[N],ans[N],siz[N],vis[N];
vector<int> e[N];
bool check(int mid){
queue<int> q;
for(int i=1;i<=n;i++) d[i] = cnt[i],f[i] = 0;
for(int i=1;i<=n;i++) if(!d[i]) q.push(i);
while(q.size()){
int u = q.front();q.pop();
f[u] = max(0,f[u]-(mid-1)),f[u]++;
if(u==1) break;
f[p[u]] += f[u];
d[p[u]]--;
if(!d[p[u]]) q.push(p[u]);
}
return f[1]==1;
}
void get_siz(){
queue<int> q;
for(int i=1;i<=n;i++) siz[i] = 1,d[i] = cnt[i];
for(int i=1;i<=n;i++) if(!d[i]) q.push(i);
while(q.size()){
int u = q.front(); q.pop();
if(u==1) break;
siz[p[u]] += siz[u];
d[p[u]]--;
if(!d[p[u]]) q.push(p[u]);
}
}
void solve(){
cin >> n;
for(int i=1;i<=n;i++) e[i].clear(),vis[i] = ans[i] = cnt[i] = 0;
for(int i=2;i<=n;i++) cin >> p[i],cnt[p[i]]++,e[p[i]].pb(i);
get_siz();
int l = 1,r = n-1,k;
while(l<=r){
int mid = (l+r)>>1;
if(check(mid)){
k = mid;
r = mid-1;
}else{
l = mid+1;
}
}
for(int i=1;i<=n;i++){
if(siz[i]-1>=k) ans[i] = 1;
}
check(k-1);
if(f[1]==2){
queue<int> q;
q.push(1),vis[1] = 1;
while(q.size()){
int u = q.front();q.pop();
for(int v:e[u]){
vis[v] = vis[u]&(f[v]!=1);
q.push(v);
}
}
for(int i=1;i<=n;i++) if(siz[i]-1==k-1 && vis[i]) ans[i] = 1;
}
for(int i=1;i<=n;i++) cout << ans[i];
cout << '\n';
}
int main(){
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
int T;cin >> T;
while(T--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 39744kb
input:
2 4 1 2 3 5 1 1 2 2
output:
1100 10000
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 164ms
memory: 43224kb
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: 196ms
memory: 67048kb
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: 278ms
memory: 67292kb
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: 150ms
memory: 41752kb
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 31066th lines differ - expected: '100', found: '000'