QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#392956 | #8134. LCA Counting | OOBMABTRAMS# | WA | 2ms | 11196kb | C++20 | 1.3kb | 2024-04-18 00:24:29 | 2024-04-18 00:24:30 |
Judging History
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'