QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#207125#6638. Treelectionsumi007WA 5ms39692kbC++142.0kb2023-10-08 09:43:102023-10-08 09:43:11

Judging History

你现在查看的是最新测评结果

  • [2023-10-08 09:43:11]
  • 评测
  • 测评结果:WA
  • 用时:5ms
  • 内存:39692kb
  • [2023-10-08 09:43:10]
  • 提交

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]);
    }
    cout << mid << ' ' << f[1] << '\n';
    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 = n;
    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: 0
Wrong Answer
time: 5ms
memory: 39692kb

input:

2
4
1 2 3
5
1 1 2 2

output:

2 1
1 4
1 4
1100
2 3
3 1
2 3
10000

result:

wrong answer 1st lines differ - expected: '1100', found: '2 1'