제출 #1014286

#제출 시각아이디문제언어결과실행 시간메모리
1014286shenfe1열쇠 (IOI21_keys)C++17
37 / 100
3042 ms50736 KiB
#include <bits/stdc++.h> #pragma GCC optimize("Ofast") #define ll long long #define lb lower_bound #define ub upper_bound #define pii pair<int,int> #define F first #define S second #define ld long double #define pb push_back #define all(v) v.begin(),v.end() #define in insert #define sz(s) (int)s.size() // #define int ll #define ppb pop_back #define mem(a,i) memset(a,i,sizeof(a)) using namespace std; const int MAX=3e5+15; const int inf=1e9; const int mod=1e9+7; const int dx[4]={1,0,-1,0}; const int dy[4]={0,1,0,-1}; vector<pii> g[MAX]; int n,m; int tov[MAX]; bool col[MAX]; vector<int> op[MAX]; vector<int> ver[MAX]; int ban[MAX]; bool bad[MAX]; struct DSU{ int f[MAX]; int s[MAX]; void init(int n){ for(int i=1;i<=n;i++)f[i]=i,s[i]=1; } int get(int v){ return (f[v]==v?v:f[v]=get(f[v])); } void unite(int u,int v){ u=get(u); v=get(v); f[v]=u; s[u]+=s[v]; } }D,D1; void mrg(int u,int v){ u=D.get(u); v=D.get(v); if(sz(ver[u])<sz(ver[v]))swap(ver[u],ver[v]); for(int x:ver[v])ver[u].pb(x); ver[v].clear(); } vector<int> find_reachable(vector<int> r,vector<int> u,vector<int> v,vector<int> c){ n=sz(r); m=sz(u); for(int i=0;i<m;i++){ u[i]++; v[i]++; g[u[i]].pb({v[i],c[i]}); g[v[i]].pb({u[i],c[i]}); } for(int i=1;i<=n;i++)ver[i].pb(i); D.init(n); D1.init(n); vector<int> comp; for(int i=1;i<=n;i++)comp.pb(i); while(!comp.empty()){ for(int x:comp)bad[x]=0; for(int x:comp){ queue<int> q; for(int to:ver[x]){ q.push(to); } vector<int> colors; while(!q.empty()&&!tov[x]){ int v=q.front(); q.pop(); colors.pb(r[v-1]); col[r[v-1]]=1; for(auto to:g[v]){ if(D.get(to.F)==D.get(v)){ continue; } else{ if(col[to.S]){ bad[x]=1; if(D1.get(D.get(v))!=D1.get(D.get(to.F))){ tov[x]=D.get(to.F); D1.unite(D.get(v),D.get(to.F)); break; } else{ int V=D.get(to.F); while(V!=x){ q.push(V); mrg(x,V); D.unite(x,V); V=D.get(tov[V]); } } } else{ colors.pb(to.S); op[to.S].pb(to.F); } } } if(tov[x])break; for(auto to:op[r[v-1]]){ if(D.get(to)==D.get(v)){ continue; } bad[x]=1; if(D1.get(D.get(v))!=D1.get(D.get(to))){ tov[x]=D.get(to); D1.unite(D.get(v),D.get(to)); break; } else{ int V=D.get(to); // cerr<<v<<" "<<to<<" "<<r[v-1]<<"\n"; while(V!=x){ // cerr<<x<<" "<<V<<" "<<tov[V]<<"\n"; q.push(V); mrg(x,V); D.unite(x,V); V=D.get(tov[V]); } } } op[r[v-1]].clear(); } for(int f:colors){ col[f]=0; op[f].clear(); } } vector<int> ncomp; for(int x:comp){ if(tov[x]==0){ if(!bad[x])ban[x]=1; else ncomp.pb(x); } } comp=ncomp; } int ans=inf; for(int i=1;i<=n;i++){ if(D.get(i)==i){ // cout<<ban[i]<<" "; if(ban[i]==1){ ans=min(ans,D.s[i]); } } } vector<int> res(n,0); for(int i=1;i<=n;i++){ if(ban[D.get(i)]==1&&D.s[D.get(i)]==ans){ res[i-1]=1; } } return res; }
#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...