| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 821559 | alvingogo | Keys (IOI21_keys) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
}
st[r[a]].clear();
while(nw[a].size){
auto h=nw[a].back();
nw[a].pop_back();
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);
}
st[r[a]].clear();
}
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;
}