Submission #1098088

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1098088	2024-10-09T04:17:23 Z	Warinchai	Tree Rotations (POI11_rot)	C++14	0 / 100	1000 ms	28772 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){
        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;
    if(adj[u].size()==0)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<<"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";
    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++){
                tans1+=fw.fans(1,val[rvid[i]]);
                tans2+=fw.fans(val[rvid[i]],id);
            }
            //cerr<<"work\n";
            for(int i=in[x];i<=out[x];i++){
                //cerr<<i<<" "<<rvid[i]<<"\n";
                fw.upd(val[rvid[i]],1);
            }
            //cerr<<"work\n";
            ans=min(tans1,tans2);
            rans[u]+=ans;
        }
    }
    if(del){
        for(int i=in[u];i<=out[u];i++)fw.upd(val[rvid[i]],-1);
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>l;
    int cnt=0;
    int rt=++id;
    build(rt);
    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);
    cout<<rans[rt]<<"\n";
}

Compilation message

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

Subtask #1
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1034 ms	9816 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1006 ms	9816 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1061 ms	9820 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1025 ms	10328 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1057 ms	11356 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1066 ms	14332 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1032 ms	21840 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1044 ms	20716 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1065 ms	27216 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1057 ms	28324 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #11
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1055 ms	28772 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-