This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
int id=0;
int l;
vector<int>adj[500005];
int val[500005];
int sz[500005];
int hv[500005];
int in[500005];
int out[500005];
int cur=0;
int rans[500005];
int rvid[500005];
int n;
struct fenwick{
int info[500005];
void upd(int id,int val){
assert(id!=0);
for(int i=id;i<=500005;i+=i&-i)info[i]+=val;
}
int fsum(int id){
int sum=0;
for(int i=id;i>0;i-=i&-i)sum+=info[i];
return sum;
}
int fans(int l,int r){
return fsum(r)-fsum(l-1);
}
}fw;
void build(int u){
//cerr<<"work\n";
int p=0;cin>>p;
if(p==0){
adj[u].push_back(++id);
build(id);
adj[u].push_back(++id);
build(id);
}else{
val[u]=p;
}
}
void print(int u){
//cerr<<"print:"<<u<<"\n";
for(auto x:adj[u])print(x);
}
void dfssz(int u){
in[u]=++cur;
rvid[cur]=u;
sz[u]=1;
for(auto x:adj[u]){
dfssz(x);
if(sz[x]>sz[hv[u]])hv[u]=x;
sz[u]+=sz[x];
}
out[u]=cur;
}
void sack(int u,int del){
//cerr<<u<<" "<<del<<"\n";
if(adj[u].size()==0){
//cerr<<"in child\n";
if(!del)fw.upd(val[u],1)/*,cerr<<"add:"<<u<<"\n"*/;
//cerr<<"child work\n";
return;
}
for(auto x:adj[u])if(x!=hv[u]){
sack(x,1);
}
if(hv[u]!=0)sack(hv[u],0);
//cerr<<u<<" "<<del<<" done vis\n";
//cerr<<"info:"<<u<<"\n";
for(auto x:adj[u]){
//cerr<<"add info:"<<x<<"\n";
rans[u]+=rans[x];
if(x!=hv[u]){
//cerr<<"work\n";
int ans=0;
int tans1=0;
int tans2=0;
for(int i=in[x];i<=out[x];i++){
if(val[rvid[i]]==0)continue;
tans1+=fw.fans(1,val[rvid[i]]);
tans2+=fw.fans(val[rvid[i]],id);
//cerr<<rvid[i]<<" "<<val[rvid[i]]<<" "<<tans1<<" "<<tans2<<"\n";
}
//cerr<<"work\n";
for(int i=in[x];i<=out[x];i++){
//cerr<<i<<" "<<rvid[i]<<"\n";
if(val[rvid[i]]!=0)fw.upd(val[rvid[i]],1)/*,cerr<<"add:"<<rvid[i]<<"\n"*/;
}
//cerr<<"work\n";
ans=min(tans1,tans2);
rans[u]+=ans;
}
}
if(del){
for(int i=in[u];i<=out[u];i++)if(val[rvid[i]]!=0)fw.upd(val[rvid[i]],-1)/*,cerr<<"delete:"<<rvid[i]<<"\n"*/;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>l;
int cnt=0;
int rt=++id;
build(rt);
//cerr<<"val:\n";
//for(int i=1;i<=id;i++)cerr<<val[i]<<" ";
//cerr<<"\n";
dfssz(rt);
//cerr<<"end build:\n";
//for(int i=1;i<=5;i++)cerr<<in[i]<<" "<<out[i]<<"\n";
//cerr<<"\n";
//print(rt);
//cerr<<"\n";
sack(rt,0);
//cerr<<"ans:\n";
//for(int i=1;i<=id;i++)cerr<<rans[i]<<"\n";
cout<<rans[rt]<<"\n";
}
/*
7
0
0
0
1
2
0
3
4
0
0
5
6
7
7
0
0
0
4
3
0
2
1
0
0
6
7
5
*/
Compilation message (stderr)
rot.cpp: In function 'int main()':
rot.cpp:103:9: warning: unused variable 'cnt' [-Wunused-variable]
103 | int cnt=0;
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |