oj.uz

Submission #1098250

# Submission time Handle Problem Language Result Execution time Memory
1098250 2024-10-09T07:05:50 Z Warinchai Tree Rotations (POI11_rot) C++14
100 / 100
 242 ms 52820 KB 
#include<bits/stdc++.h>
#define int long long
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"*/;
    }
}
int32_t 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 'int32_t main()':
rot.cpp:105:9: warning: unused variable 'cnt' [-Wunused-variable]
  105 |     int cnt=0;
      |         ^~~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12252 KB Output is correct
2 Correct 5 ms 12124 KB Output is correct
3 Correct 5 ms 12316 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 12380 KB Output is correct
2 Correct 5 ms 12428 KB Output is correct
3 Correct 5 ms 12216 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 6 ms 13148 KB Output is correct
2 Correct 7 ms 12948 KB Output is correct
3 Correct 6 ms 13000 KB Output is correct
4 Correct 7 ms 13148 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14940 KB Output is correct
2 Correct 14 ms 14204 KB Output is correct
3 Correct 30 ms 16724 KB Output is correct
4 Correct 11 ms 14940 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 20048 KB Output is correct
2 Correct 33 ms 21332 KB Output is correct
3 Correct 31 ms 23384 KB Output is correct
4 Correct 44 ms 23888 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 31696 KB Output is correct
2 Correct 40 ms 29020 KB Output is correct
3 Correct 52 ms 26960 KB Output is correct
4 Correct 41 ms 25948 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 31056 KB Output is correct
2 Correct 56 ms 32592 KB Output is correct
3 Correct 56 ms 35984 KB Output is correct
4 Correct 56 ms 35640 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 42580 KB Output is correct
2 Correct 134 ms 41296 KB Output is correct
3 Correct 98 ms 41044 KB Output is correct
4 Correct 115 ms 40276 KB Output is correct
5 Correct 222 ms 38896 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 42580 KB Output is correct
2 Correct 110 ms 49744 KB Output is correct
3 Correct 149 ms 47700 KB Output is correct
4 Correct 93 ms 51132 KB Output is correct
5 Correct 242 ms 42580 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 43344 KB Output is correct
2 Correct 100 ms 45904 KB Output is correct
3 Correct 166 ms 43740 KB Output is correct
4 Correct 138 ms 43860 KB Output is correct
5 Correct 109 ms 52820 KB Output is correct
6 Correct 235 ms 43460 KB Output is correct