Submission #525708

#TimeUsernameProblemLanguageResultExecution timeMemory
525708leakedSimurgh (IOI17_simurgh)C++14
13 / 100
234 ms7412 KiB
#include "simurgh.h" #include <bits/stdc++.h> #define f first #define s second #define vec vector #define pb push_back #define all(x) (x).begin(),(x).end() #define rall(x) (x).rbegin(),(x).rend() #define m_p make_pair #define sz(x) (int)(x).size() #define pw(x) (1LL<<(x)) using namespace std; const int N=5e2+10; typedef pair<int,int> pii; struct dsu{ int p[N],sz[N]; void make(int v){ p[v]=v; sz[v]=1; } void init(){ for(int i=0;i<N;i++) make(i); } int get(int v){ return p[v]=(p[v]==v?v:get(p[v])); } bool mg(int a,int b){ a=get(a),b=get(b); if(a==b) return 0; if(sz[a]>sz[b]) swap(a,b); p[a]=b;sz[b]+=sz[a]; return 1; } }ds; vec<array<int,4>> goods; vec<int> ones; bool used[N*N]; int pr[N]; int ids[N]; bool ema[N*N]; int clr[N*N]; int u[N]; vec<array<int,3>> backt; vec<array<int,3>> inc; vec<pii> g[N]; int get(vec<array<int,3>> vc){ ds.init(); vec<int>asks; for(auto &z : vc){ assert(ds.mg(z[0],z[1])); asks.pb(z[2]); } int hv=0; for(auto &z : goods){ if(ds.mg(z[0],z[1])){ hv-=z[3]; asks.pb(z[2]); // cout<<"DELETE "<<z[0]<<' '<<z[1]<<' '<<z[2]<<' '<<z[3]<<endl; } } hv+=count_common_roads(asks); // if(hv<0){ // cout<<"EBLAN "<<endl; // for(auto &zt : asks){ // cout<<zt<<endl; // } // cout<<endl; // } return hv; } void rec(vec<array<int,3>> vc, int have){ if(!have || sz(vc)==0) return; if(sz(vc)==1){ goods.pb({vc[0][0],vc[0][1],vc[0][2],1}); return; } ds.init(); vec<array<int,3>> lft,rgt; for(int i=0;i<sz(vc)/2;i++) lft.pb(vc[i]); for(int i=sz(lft);i<sz(vc);i++) rgt.pb(vc[i]); // for(auto &z : vc) // cout<<z[0]<<' '<<z[1]<<endl; // cout<<"HAVE "<<have<<endl; int hv=get(lft); rec(lft,hv); rec(rgt,have-hv); } void dfs(int v,int p){ u[v]=1; for(auto &z : g[v]){ if(z.f==p || u[z.f]==2) continue; if(u[z.f]==1){ backt.pb({v,z.f,z.s}); } else{ pr[z.f]=v; ids[z.f]=z.s; inc.pb({v,z.f,z.s}); dfs(z.f,v); } } u[v]=2; } vec<int> find_roads(int n, vec<int> v,vec<int> u){ int m=sz(v); for(int i=0;i<m;i++){ g[v[i]].pb({u[i],i}); g[u[i]].pb({v[i],i}); } dfs(0,0); int ostov=get(inc); for(auto &z : backt){ int v=z[0]; vec<array<int,3>>idk; int iam1=-1; if(z[2]==48){ cout<<"IMG "<<endl; z[2]=48; } while(v!=z[1]){ if(!used[ids[v]]){ vec<array<int,3>> toask; for(auto &zt : inc){ if(zt[2]!=ids[v]) toask.pb(zt); } toask.pb(z); int me=get(toask); if(me==ostov){ idk.pb({v,pr[v],ids[v]}); } else{ if(me>ostov){ goods.pb({v,pr[v],ids[v],0}); iam1=1; clr[ids[v]]=0; clr[z[2]]=1; goods.pb({z[0],z[1],z[2],1}); } else{ goods.pb({v,pr[v],ids[v],1}); iam1=0; clr[ids[v]]=1; clr[z[2]]=0; goods.pb({z[0],z[1],z[2],0}); } used[z[2]]=1; used[ids[v]]=1; } } v=pr[v]; } if(sz(idk)){ if(iam1==-1){ v=z[0]; while(v!=z[1]){ int j=ids[v]; if(used[j]){ int cv=clr[j]; vec<array<int,3>> toask; for(auto &zt : inc){ if(zt[2]!=ids[v]) toask.pb(zt); } toask.pb(z); int me=get(toask); if(me==ostov){ iam1=cv; clr[z[2]]=cv; } else{ if(me<ostov){ assert(cv); iam1=0; clr[z[2]]=0; } else{ assert(!cv); iam1=1; clr[z[2]]=1; } } break; } v=pr[v]; } if(iam1==-1){ iam1=0; } } goods.pb({z[0],z[1],z[2],clr[z[2]]}); used[z[2]]=1; for(auto &z : idk){ goods.pb({z[0],z[1],z[2],iam1}); clr[z[2]]=iam1; // cout<<z[2]<<endl; used[z[2]]=1; } } // cout<<"ALWAYS "<<z[2]<<endl<<endl; // for(auto &q : goods){ // cout<<q[2]<<endl; // } // cout<<endl; } // for(auto &z : goods){ // cout<<"KNOW "<<z[0]<<' '<<z[1]<<' '<<z[2]<<' '<<z[3]<<endl; // } // exit(0); for(auto &z : inc){ if(!used[z[2]]){ goods.pb({z[0],z[1],z[2],1}); used[z[2]]=1; } // cout<<"INC "<<z[0]<<' '<<z[1]<<endl; } sort(all(goods));goods.erase(unique(all(goods)),goods.end()); // for(auto &z : goods){ // cout<<"KNOW "<<z[0]<<' '<<z[1]<<' '<<z[2]<<' '<<z[3]<<endl; // } // return ones; for(int i=0;i<n;i++){ vec<array<int,3>>kekw; for(auto &z : g[i]){ if(!used[z.s]){ kekw.pb({i,z.f,z.s}); used[z.s]=1; } } if(sz(kekw)){ rec(kekw,get(kekw)); } } for(auto &z : goods){ if(z[3]==1) ones.pb(z[2]); } return ones; } /* 4 6 0 1 0 2 0 3 1 2 1 3 2 3 0 1 5 6 7 0 1 1 2 2 3 2 4 4 5 0 2 1 5 0 2 4 5 6 */
#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...