oj.uz

Submission #1098225

# Submission time Handle Problem Language Result Execution time Memory
1098225 2024-10-09T06:36:16 Z Warinchai Tree Rotations (POI11_rot) C++14
63 / 100
 161 ms 31316 KB 
#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

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 6 ms 12120 KB Output is correct
2 Correct 5 ms 12124 KB Output is correct
3 Correct 5 ms 12124 KB Output is correct
4 Correct 5 ms 12060 KB Output is correct
5 Correct 5 ms 12124 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12124 KB Output is correct
2 Correct 6 ms 12380 KB Output is correct
3 Correct 5 ms 12120 KB Output is correct
4 Correct 5 ms 12380 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12892 KB Output is correct
2 Correct 7 ms 12636 KB Output is correct
3 Correct 7 ms 12792 KB Output is correct
4 Correct 6 ms 12892 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14220 KB Output is correct
2 Correct 12 ms 13404 KB Output is correct
3 Correct 30 ms 14940 KB Output is correct
4 Correct 11 ms 13912 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 16656 KB Output is correct
2 Correct 28 ms 18256 KB Output is correct
3 Correct 32 ms 20048 KB Output is correct
4 Correct 33 ms 20060 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 26452 KB Output is correct
2 Correct 36 ms 23636 KB Output is correct
3 Correct 50 ms 21668 KB Output is correct
4 Correct 39 ms 20564 KB Output is correct

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 10.0

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