Submission #1098225

#TimeUsernameProblemLanguageResultExecution timeMemory
1098225WarinchaiUntitled (POI11_rot)C++14
63 / 100
161 ms31316 KiB
#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 (stderr)

rot.cpp: In function 'int main()':
rot.cpp:103:9: warning: unused variable 'cnt' [-Wunused-variable]
  103 |     int cnt=0;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...