Submission #1098215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098215		Warinchai	Untitled (POI11_rot)	C++14	63 / 100	174 ms	30408 KiB

Main

#include<bits/stdc++.h>
using namespace std;
int id=0;
int l;
vector<int>adj[400005];
int val[400005];
int sz[400005];
int hv[400005];
int in[400005];
int out[400005];
int cur=0;
int rans[400005];
int rvid[400005];
int n;
struct fenwick{
    int info[400005];
    void upd(int id,int val){
        assert(id!=0);
        for(int i=id;i<=400005;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
*/

Compilation message (stderr)

rot.cpp: In function 'int main()':
rot.cpp:103:9: warning: unused variable 'cnt' [-Wunused-variable]
  103 |     int cnt=0;
      |         ^~~

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 10