oj.uz

Submission #1098215

# Submission time Handle Problem Language Result Execution time Memory
1098215 2024-10-09T06:30:23 Z Warinchai Tree Rotations (POI11_rot) C++14
63 / 100
 174 ms 30408 KB 
#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

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 5 ms 9820 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9820 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 5 ms 9860 KB Output is correct
3 Correct 4 ms 9932 KB Output is correct
4 Correct 7 ms 10076 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10588 KB Output is correct
2 Correct 9 ms 10204 KB Output is correct
3 Correct 5 ms 10588 KB Output is correct
4 Correct 5 ms 10588 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11864 KB Output is correct
2 Correct 12 ms 11096 KB Output is correct
3 Correct 28 ms 12636 KB Output is correct
4 Correct 11 ms 11868 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14884 KB Output is correct
2 Correct 26 ms 16216 KB Output is correct
3 Correct 46 ms 18056 KB Output is correct
4 Correct 46 ms 18284 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 24848 KB Output is correct
2 Correct 43 ms 21856 KB Output is correct
3 Correct 49 ms 19772 KB Output is correct
4 Correct 38 ms 18740 KB Output is correct

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 21840 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 174 ms 30408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 108 ms 29664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 103 ms 30036 KB Output isn't correct
2 Halted 0 ms 0 KB -