Submission #1058444

#TimeUsernameProblemLanguageResultExecution timeMemory
1058444shenfe1Simurgh (IOI17_simurgh)C++17
100 / 100
163 ms15556 KiB
#include <bits/stdc++.h> #include "simurgh.h" #pragma GCC optimize("Ofast") using namespace std; #define pb push_back #define pii pair<int,int> #define sz(s) (int)s.size() #define F first #define S second #define all(v) v.begin(),v.end() const int MAX=2e5+10; struct dsu{ int f[MAX]; void init(int n){ for(int i=0;i<n;i++)f[i]=i; } int get(int v){ return (f[v]==v?v:f[v]=get(f[v])); } void unite(int a,int b){ a=get(a),b=get(b); f[a]=b; } }d; int n; vector<pii> g[MAX]; vector<int> u,v; int is1[MAX],is0[MAX],dn[MAX]; int pr[MAX],dep[MAX]; set<int> st; void dfs(int st){ queue<int> q; q.push(st); while(!q.empty()){ int v=q.front(); q.pop(); for(auto to:g[v]){ if(pr[v]==to.S)continue; dep[to.F]=dep[v]+1; pr[to.F]=to.S; q.push(to.F); } } } int cq=1; vector<int> vc(set<int> &st){ vector<int> res; for(int i:st)res.pb(i); return res; } int add(vector<int> &vec){ int CNT=0; d.init(n); vector<int> x; for(int i:vec){ x.pb(i); d.unite(u[i],v[i]); } for(int i:st){ if(d.get(u[i])!=d.get(v[i])){ CNT+=is1[i]; d.unite(u[i],v[i]); x.pb(i); } } cq++; // assert(cq<=8000); return count_common_roads(x)-CNT; } vector<int> find_roads(int N,vector<int> U,vector<int> V){ n=N; u=U; v=V; vector<int> e; d.init(n); for(int i=0;i<sz(U);i++){ if(d.get(U[i])!=d.get(V[i])){ d.unite(U[i],V[i]); g[U[i]].pb({V[i],i}); g[V[i]].pb({U[i],i}); st.insert(i); } else e.pb(i); } for(int i=0;i<sz(U);i++)dn[i]=1; for(int i=0;i<n;i++)pr[i]=-1; dfs(0); int cnt=count_common_roads(vc(st)); for(int num:e){ int a=U[num],b=V[num]; vector<int> canzam; int allv=0; int CNT=0; while(a!=b){ CNT++; if(CNT>N){ return vector<int>(n,-1); } if(dep[a]>dep[b]){ canzam.pb(pr[a]); if(U[pr[a]]==a)a=V[pr[a]]; else a=U[pr[a]]; } else{ canzam.pb(pr[b]); if(U[pr[b]]==b)b=V[pr[b]]; else b=U[pr[b]]; } } int ok=0; int canEdge=-1; for(int edge:canzam){ if(dn[edge])allv=1; if(is1[edge]){ ok=1; canEdge=edge; } else if(is0[edge]){ ok=2; canEdge=edge; } } if(!allv)continue; if(ok==0){ for(int edge:canzam){ assert(dn[edge]); st.erase(edge); st.insert(num); cq++; int ncnt=count_common_roads(vc(st)); if(ncnt<cnt){ dn[edge]=0; is1[edge]=1; dn[num]=0; is0[num]=1; } else if(ncnt>cnt){ dn[edge]=0; is0[edge]=1; dn[num]=0; is1[num]=1; } st.insert(edge); st.erase(num); } if(dn[num]){ dn[num]=0; is0[num]=1; for(int edge:canzam){ dn[edge]=0; is0[edge]=1; } } else{ for(int edge:canzam){ if(dn[edge]){ dn[edge]=0; is0[edge]=is0[num]; is1[edge]=is1[num]; } } } } else if(ok==1){ st.erase(canEdge); st.insert(num); int ncnt=count_common_roads(vc(st)); cq++; st.insert(canEdge); st.erase(num); dn[num]=0; if(ncnt==cnt){ is1[num]=1; } else{ is0[num]=1; } } else{ st.erase(canEdge); st.insert(num); int ncnt=count_common_roads(vc(st)); cq++; st.insert(canEdge); st.erase(num); dn[num]=0; if(ncnt==cnt){ is0[num]=1; } else{ is1[num]=1; } } for(int edge:canzam){ if(dn[edge]){ dn[edge]=0; st.insert(num); st.erase(edge); cq++; int ncnt=count_common_roads(vc(st)); st.erase(num); st.insert(edge); if(ncnt==cnt){ is0[edge]=is0[num]; is1[edge]=is1[num]; } else{ is0[edge]=1-is0[num]; is1[edge]=1-is1[num]; } } } } assert(cq<=2*n+1); for(int edge:st){ if(dn[edge]){ dn[edge]=0; is1[edge]=1; } } for(int i=0;i<n;i++){ g[i].clear(); } for(int i=0;i<sz(u);i++){ g[u[i]].pb({v[i],i}); g[v[i]].pb({u[i],i}); } for(int i=0;i<n;i++){ vector<int> vec; for(auto to:g[i]){ if(!st.count(to.S)&&i>=to.F)vec.pb(to.S); } int cnt=add(vec); // cout<<i<<" "<<cnt<<"\n"; for(int j=1;j<=cnt;j++){ int l=0,r=sz(vec)-1,res=sz(vec)-1; // cerr<<l<<" "<<r<<"\n"; while(l<=r){ int mid=(l+r)/2; vector<int> v; for(int j=0;j<=mid;j++){ if(!st.count(vec[j]))v.pb(vec[j]); } if(add(v)>=j){ r=mid-1; res=mid; } else l=mid+1; } is1[vec[res]]=1; } } vector<int> ans; for(int i=0;i<sz(u);i++)if(is1[i])ans.pb(i); 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...