제출 #1066213

#제출 시각아이디문제언어결과실행 시간메모리
1066213epicci23열쇠 (IOI21_keys)C++17
100 / 100
990 ms123592 KiB
#include "bits/stdc++.h" #define all(v) v.begin() , v.end() #define sz(a) (int)a.size() using namespace std; const int N = 3e5 + 5; vector<int> v[N],comp[N]; set<array<int,2>> adj[N]; set<int> s[N]; bool vis[N],vis2[N],mark[N]; vector<int> cur,par(N,0); void merge_info(int a,int b){ a=par[a],b=par[b]; if(a==b) return; if(sz(comp[a])+sz(s[a])+sz(adj[a])+sz(v[a]) <sz(comp[b])+sz(s[b])+sz(adj[b])+sz(v[b])) swap(a,b); mark[a]&=mark[b]; for(int x:v[b]) v[a].push_back(x); for(int x:comp[b]){ comp[a].push_back(x); par[x]=a; } for(array<int,2> x:adj[b]){ if(s[a].count(x[0])) v[a].push_back(x[1]); else adj[a].insert(x); } for(int u:s[b]){ if(s[a].count(u)) continue; s[a].insert(u); auto it=adj[a].lower_bound({u,0}); while(it!=adj[a].end() && (*it)[0]==u){ v[a].push_back((*it)[1]); adj[a].erase(*it); it=adj[a].lower_bound({u,0}); } } adj[b].clear(); v[b].clear(); comp[b].clear(); s[b].clear(); } void dfs(int c){ vis2[c]=vis[c]=1; cur.push_back(c); while(!v[par[c]].empty()){ int x=v[par[c]].back(); v[par[c]].pop_back(); if(vis[x] && !vis2[x]){ mark[par[c]]=0; continue; } if(vis[x]==1){ while(!cur.empty() && par[cur.back()]!=par[x]){ merge_info(cur.back(),x); cur.pop_back(); } } else{ dfs(x); if(par[c]!=par[x]) mark[par[c]]=0; } } if(!cur.empty() && cur.back()==c) cur.pop_back(); vis2[c]=0; } vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C){ int n=sz(R),m=sz(U); iota(all(par),0); for(int i=0;i<n;i++){ mark[i]=1; comp[i].push_back(i); s[i].insert(R[i]); } for(int i=0;i<m;i++){ int a=U[i],b=V[i],c=C[i]; if(s[a].count(c)) v[a].push_back(b); else adj[a].insert({c,b}); if(s[b].count(c)) v[b].push_back(a); else adj[b].insert({c,a}); } for(int i=0;i<n;i++) if(!vis[i]) dfs(i); int mini=100000007; for(int i=0;i<n;i++) if(mark[par[i]]) mini=min(mini,sz(comp[par[i]])); vector<int> ans(n,0); for(int i=0;i<n;i++) if(mark[par[i]] && sz(comp[par[i]])==mini) ans[i]=1; return ans; } /*void _(){ int n,m; cin >> n >> m; iota(all(par),0); for(int i=0;i<n;i++) comp[i].push_back(i); vector<int> col(n); for(int i=0;i<n;i++) cin >> col[i]; for(int i=0;i<n;i++) s[i].insert(col[i]); for(int i=0;i<m;i++){ int a,b,c; cin >> a >> b >> c; v[a][c].push_back(b); v[b][c].push_back(a); } for(int i=0;i<n;i++) if(vis[i]==0) dfs(i); int mini=100000007; for(int i=0;i<n;i++){ if(mark[par[i]]) continue; mini=min(mini,sz(comp[par[i]])); } vector<int> ans(n,0); for(int i=0;i<n;i++) if(!mark[par[i]] && sz(comp[par[i]])==mini) ans[i]=1; for(int i=0;i<n;i++) cout << ans[i] << " \n"[i==n-1]; } int32_t main(){ cin.tie(0); ios::sync_with_stdio(0); int tc=1;//cin >> tc; while(tc--) _(); return 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...