제출 #821553

#제출 시각아이디문제언어결과실행 시간메모리
821553alvingogo열쇠 (IOI21_keys)C++17
0 / 100
1 ms340 KiB
#include <vector> #include <bits/stdc++.h> #define fs first #define sc second #define p_q priority_queue using namespace std; struct DSU{ vector<int> bo; void init(int n){ bo.resize(n); iota(bo.begin(),bo.end(),0); } int find(int x){ return bo[x]==x?x:bo[x]=find(bo[x]); } void merge(int x,int y){ bo[x]=y; } }dsu; vector<int> r,dfn,low,out,inv; vector<vector<int> > nw; vector<vector<pair<int,int> > > e; vector<vector<pair<int,int> > > st; int cnt=1; void dfs(int a,int f){ dfn[a]=low[a]=out[a]=cnt; inv[cnt]=a; cnt++; for(auto h:e[a]){ st[h.fs].push_back({a,h.sc}); } for(auto h:st[r[a]]){ nw[dsu.find(h.fs)].push_back(h.sc); } for(auto h:nw[a]){ if(dfn[h]){ low[a]=min(low[a],dfn[h]); continue; } dfs(h,a); low[a]=min(low[a],low[h]); out[a]=out[h]; for(auto h:st[r[a]]){ nw[dsu.find(h.fs)].push_back(h.sc); } } dsu.merge(a,f); } vector<int> find_reachable(vector<int> R, vector<int> u, vector<int> v, vector<int> c) { int n=R.size(); int m=u.size(); dsu.init(n); e.resize(n); dfn.resize(n); low.resize(n); nw.resize(n); out.resize(n); inv.resize(n+1); st.resize(n); r=R; for(int i=0;i<m;i++){ e[u[i]].push_back({c[i],v[i]}); e[v[i]].push_back({c[i],u[i]}); } for(int i=0;i<n;i++){ if(!dfn[i]){ dfs(i,i); } } int mn=1e9; for(int i=0;i<n;i++){ if(dfn[i]==low[i]){ mn=min(mn,out[i]-dfn[i]+1); } } vector<int> ans(n); for(int i=0;i<n;i++){ if(dfn[i]==low[i]){ if(out[i]-dfn[i]+1==mn){ for(int j=dfn[i];j<=out[i];j++){ ans[inv[j]]=1; } } } } 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...