| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 598579 | definitelynotmee | 열쇠 (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<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename t>
using matrix = vector<vector<t>>;
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
vector<int> ans(r.size(), 1);
int n = r.size();
matrix<pii> g(n);
for(int i = 0; i < u.size(); i++){
g[u[i]].push_back({v[i],c[i]});
g[v[i]].push_back({u[i],c[i]});
}
if(n <= 2000){
for(int root = 0; root < n; root++){
vector<int> check(n), got(n);
matrix<int> whenget(n);
vector<int> st = {root};
while(!st.empty()){
int cur = st.back();
st.pop_back();
if(check[cur])
continue;
check[cur] = 1;
got[r[cur]] = 1;
while(!whenget[r[cur]].empty()){
st.push_back(whenget[r[cur]].back());
whenget[r[cur]].pop_back();
}
for(pii i : g[cur]){
if(got[i.ss])
st.push_back(i.ff);
else whenget[i.ss].push_back(i.ff);
}
}
ans[root] = accumulate(all(check),0);
}
int mini = *min_element(all(ans));
for(int i = 0; i < n; i++)
ans[i] = ans[i] == mini;
} else {
vector<int> color(n);
for(int i = 0; i < n; i++)
color[i] = 1<<c[i];
int try = 30;
vector<int> scc(n);
while(try--){
fill(all(scc),0);
vector<int> check(n), combcolor(n);
vector<int> out;
auto dfs =[&](int id, auto dfs)->void{
check[id] = 1;
for(pii i : g[id]){
if(((1<<i.ss)&color[id])&&!check[i.ff])
dfs(i.ff,dfs);
}
out.push_back(id);
};
for(int i = 0; i < n; i++){
if(!check[i])
dfs(i,dfs);
}
int timer = -1;
auto rdfs =[&](int id, auto dfs)->void{
check[id] = 2;
scc[id] = timer;
combcolor|=color[id];
for(pii i : g[id]){
if(((1<<i.ss)&color[i.ff])&&check[i.ff]!=2)
dfs(i.ff,dfs);
}
}
for(int i = 0; i < n; i++){
if(check[out[i]]!=2)
timer++,rdfs(out[i],rdfs);
}
for(int i = 0; i < n; i++){
color[i] = combcolor[scc[i]];
}
}
vector<int> isvalid(n,1), sz(n,1<<30);
for(int v = 0; v < n; v++){
for(pii i : g[v]){
if(((1<<i.ss)&color[v])&&scc[i.ff]!=scc[v])
isvalid[v] = 0;
}
if(sz[scc[v]] == 1<<30)
sz[scc[v]] = 0;
sz[scc[v]]++;
}
int mini = 1<<30;
for(int i = 0; i < n; i++)
if(isvalid[i]) mini = min(mini,sz[i]);
for(int i = 0; i < n; i++){
ans[i] = sz[scc[i]] == mini;
}
}
return ans;
}