제출 #242961

#제출 시각아이디문제언어결과실행 시간메모리
242961thebesSimurgh (IOI17_simurgh)C++14
100 / 100
213 ms6652 KiB
#include "simurgh.h" #include <bits/stdc++.h> #define DEBUG 1 using namespace std; namespace output{ void __(short x){cout<<x;} void __(unsigned x){cout<<x;} void __(int x){cout<<x;} void __(long long x){cout<<x;} void __(unsigned long long x){cout<<x;} void __(double x){cout<<x;} void __(long double x){cout<<x;} void __(char x){cout<<x;} void __(const char*x){cout<<x;} void __(const string&x){cout<<x;} void __(bool x){cout<<(x?"true":"false");} template<class S,class T> void __(const pair<S,T>&x){__(DEBUG?"(":""),__(x.first),__(DEBUG?", ":" "),__(x.second),__(DEBUG?")":"");} template<class T> void __(const vector<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} template<class T> void __(const set<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} template<class T> void __(const multiset<T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} template<class S,class T> void __(const map<S,T>&x){__(DEBUG?"{":"");bool _=0;for(const auto&v:x)__(_?DEBUG?", ":" ":""),__(v),_=1;__(DEBUG?"}":"");} void pr(){cout<<"\n";} template<class S,class... T> void pr(const S&a,const T&...b){__(a);if(sizeof...(b))__(' ');pr(b...);} } using namespace output; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<int,char> pic; typedef pair<double,double> pdd; typedef pair<ld,ld> pld; typedef vector<int> vi; typedef vector<ll> vl; #define pb push_back #define eb emplace_back #define fox(i,x,y) for(int i=(x);i<=(y);i++) #define foxr(i,x,y) for(int i=(y);i>=(x);i--) #define F first #define S second const int MN = 505; int N, M, i, x, y, bk[MN], par[MN], id[MN], use[MN], vs[MN], val[MN*MN], dep[MN], ds[MN]; vector<pii> adj[MN], tr[MN]; vi wew, ans, tmp, a, b; pii meh[MN]; void dfs(int n,int p){ vs[n] = 1; meh[n] = {1<<30, 0}; for(auto v : adj[n]){ if(vs[v.F]){ if(v.F==p) continue; if(dep[v.F]<meh[n].F) meh[n]={dep[v.F],v.S}; } else{ dep[v.F] = dep[n]+1; par[v.F] = n; id[v.F] = v.S; dfs(v.F, n); wew.pb(v.S); tr[n].pb(v); tr[v.F].pb({n,v.S}); if(meh[v.F].F<meh[n].F) meh[n]=meh[v.F]; } } if(meh[n].F<dep[n]) bk[n]=meh[n].S; } inline void ini(){tmp.clear(); for(int _=0;_<N;_++)ds[_]=_;} int fnd(int x){return ds[x]=x==ds[x]?x:fnd(ds[x]);} inline bool uni(int x,int y){ x=fnd(x), y=fnd(y); if(x!=y){ds[x]=y; return 1;} else return 0; } inline int treeify(){ int res=0; for(auto v : wew){ if(uni(a[v],b[v])){ tmp.pb(v); res += val[v]; } } return res; } vi find_roads(int n,vi u,vi v){ N = n; M = (int)u.size(); for(i=0;i<M;i++){ adj[u[i]].pb({v[i],i}); adj[v[i]].pb({u[i],i}); } a=u, b=v; memset(bk,-1,sizeof(bk)); dfs(0,-1); memset(val, -1, sizeof(val)); int init = count_common_roads(wew); for(i=1;i<N;i++){ if(bk[i]==-1) val[id[i]]=1; else{ if(val[bk[i]]==-1){ int ed = bk[i]; x=u[ed], y=v[ed]; if(dep[x]<dep[y]) swap(x,y); int dn = -1; vi acc; while(x!=y){ if(~val[id[x]]){ dn = id[x]; break; } acc.pb(id[x]); x = par[x]; } if(~dn){ wew.erase(find(wew.begin(),wew.end(),dn)); wew.pb(bk[i]); int res = count_common_roads(wew); wew.erase(find(wew.begin(),wew.end(),bk[i])); wew.pb(dn); val[bk[i]] = res-init+val[dn]; } else{ int mx = init; vi res; for(auto v : acc){ wew.erase(find(wew.begin(),wew.end(),v)); wew.pb(bk[i]); res.pb(count_common_roads(wew)); mx = max(res.back(), mx); wew.pop_back(); wew.pb(v); } int fl=0; for(auto v : res){ if(v!=mx) fl=1; } if(fl){ for(int j=0;j<(int)acc.size();j++){ if(res[j]!=mx) val[acc[j]]=1; else val[acc[j]]=0; } if(init!=mx) val[bk[i]]=1; else val[bk[i]]=0; } else{ for(int j=0;j<(int)acc.size();j++) val[acc[j]]=0; val[bk[i]]=0; } } } if(val[id[i]]==-1){ wew.erase(find(wew.begin(),wew.end(),id[i])); wew.pb(bk[i]); int res = count_common_roads(wew); wew.erase(find(wew.begin(),wew.end(),bk[i])); wew.pb(id[i]); val[id[i]] = init-res+val[bk[i]]; } } } for(i=0;i<M;i++){ if(val[i]==1) ans.pb(i); } for(i=0;i<N;i++){ vi vec; for(auto v : adj[i]){ if(val[v.S]==-1) vec.pb(v.S); } if(vec.size()){ ini(); for(auto v : vec){ tmp.pb(v); uni(a[v],b[v]); } int r = treeify(); int k = count_common_roads(tmp)-r; while(k--){ int lo=0, hi=(int)vec.size()-1; while(lo<hi){ int mid=(lo+hi)>>1; ini(); for(int j=mid+1;j<=hi;j++){ tmp.pb(vec[j]); uni(a[vec[j]],b[vec[j]]); } int r = treeify(); if(count_common_roads(tmp)-r>0) lo=mid+1; else hi=mid; } val[vec[lo]]=1; ans.pb(vec[lo]); for(int j=lo+1;j<(int)vec.size();j++) val[vec[j]]=0; vec.erase(vec.begin()+lo,vec.end()); } } } //pr(">",ans); return ans; }
#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...