| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1219088 | brinton | Keys (IOI21_keys) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
// #include "grader.cpp"
using namespace std;
vector<int> find_reachable(vector<int> R, vector<int> U, vector<int> V, vector<int> C) {
int N = R.size(),M = U.size();
vector<int> lgid;
int lgsz = N;
lgid.resize(N);
for(auto &i:R[i]) if(i > 29) i = 29;
for(auto &i:C[i]) if(i > 29) i = 29;
for(int i = 0;i < N;i++) lgid[i] = i;
while(true){
// create edges, key
vector<int> key,lsz;
key = lsz = vector<int>(lgsz,0);
for(int i = 0;i < N;i++){
key[lgid[i]] |= (1 << R[i]);
lsz[lgid[i]]++;
}
vector<set<int>> edges(lgsz);
for(int i = 0;i < M;i++){
int u = lgid[U[i]],v = lgid[V[i]],c = C[i];
if(u == v) continue;
if(key[u] & (1 << c)) edges[u].insert(v);
if(key[v] & (1 << c)) edges[v].insert(u);
}
// init;
vector<int> tin,low,gid;
tin = low = gid = vector<int>(lgsz,-1);
stack<int> st;
int gt,gsz;
gt = gsz = 0;
// scc
function<void(int,int)> tarjan = [&](int cur,int par){
tin[cur] = low[cur] = gt++;
st.push(cur);
for(auto nxt:edges[cur]){
if(gid[nxt] != -1) continue;
if(tin[nxt] != -1) {
low[cur] = min(low[cur],low[nxt]);
continue;
}
tarjan(nxt,cur);
if(low[nxt] > tin[cur]){
vector<int> gm;
while(st.top() != cur){
gm.push_back(st.top());
st.pop();
}
for(auto &i:gm) gid[i] = gsz;
gsz++;
}
low[cur] = min(low[cur],low[nxt]);
}
};
for(int i = 0;i < N;i++){
if(tin[i] == -1) {
tarjan(i,-1);
vector<int> gm;
while(!st.empty()){
gm.push_back(st.top());
st.pop();
}
for(auto &i:gm) gid[i] = gsz;
gsz++;
}
}
if(gsz == lgsz) {
// find the solution;
int minsz = INT_MAX;
for(int i = 0;i < lgsz;i++){
if(edges[i].size() == 0){
minsz = min(minsz,lsz[i]);
}
}
vector<int> ans(N,false);
for(int i = 0;i < N;i++){
int id = lgid[i];
if(edges[id].size() == 0 && lsz[id] == minsz){
ans[i] = 1;
}
}
return ans;
}
lgsz = gsz;
for(auto &i:lgid) i = gid[i];
}
}