QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#392956#8134. LCA CountingOOBMABTRAMS#WA 2ms11196kbC++201.3kb2024-04-18 00:24:292024-04-18 00:24:30

Judging History

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

  • [2024-04-18 00:24:30]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:11196kb
  • [2024-04-18 00:24:29]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=200013;
priority_queue<int>pq[N];
vector<int>mp[N];

void dfs(int x){
    if(mp[x].empty()){
        pq[x].push(0);
        return;
    }
    int k=0;
    int mx[2]={-1,-1},v;
    for(auto i:mp[x]){
        dfs(i);
        if(!pq[i].empty()){
            k=pq[i].top();
            if(k>mx[0])mx[1]=mx[0],mx[0]=k;
            else if(k>mx[1])mx[1]=k;
        }
    }
    if(mx[1]!=-1)k=1,v=1+mx[0]+mx[1];
    for(auto i:mp[x]){
        if(k){
            if(!pq[i].empty()){
                if(pq[i].top()==mx[0])mx[0]=-1,pq[i].pop();
                else if(pq[i].top()==mx[1])mx[1]=-1,pq[i].pop();
            }
        }
        if(pq[i].size()>pq[x].size())swap(pq[x],pq[i]);
        while(!pq[i].empty())pq[x].push(pq[i].top()),pq[i].pop();
    }
    if(k)pq[x].push(v);
}

void solve(){
    int n;
    cin>>n;
    for(int i=1,x;i<n;i++)cin>>x,mp[x].push_back(i+1);
    dfs(1);
    int ans=0;
    while(!pq[1].empty()){
        int x=pq[1].top();
        pq[1].pop();
        ans++,cout<<ans<<' ';
        while(x--)ans+=2,cout<<ans<<' ';
    }
    cout<<'\n';
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    while(T--)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 11196kb

input:

7
1 1 2 4 2 2

output:

1 3 5 6 

result:

ok 4 number(s): "1 3 5 6"

Test #2:

score: 0
Accepted
time: 2ms
memory: 10260kb

input:

10
1 1 2 2 1 1 1 2 4

output:

1 3 5 6 7 8 9 

result:

ok 7 numbers

Test #3:

score: 0
Accepted
time: 2ms
memory: 10768kb

input:

10
1 2 2 4 5 6 1 2 4

output:

1 3 5 7 8 

result:

ok 5 number(s): "1 3 5 7 8"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 10532kb

input:

10
1 2 3 3 3 5 6 4 9

output:

1 2 

result:

wrong answer 2nd numbers differ - expected: '3', found: '2'