| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1229242 | Ludissey | 열쇠 (IOI21_keys) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define all(a) (a.begin(), a.end())
#define rall(a) a.rbegin(), a.rend()
#define sz(a) (int)a.size()
vector<int> sz,parent;
vector<vector<int>> neigh;
vector<vector<int>> neighu;
vector<int> topo;
vector<int> visited;
bool unt=true;
int geP(int a){
if(parent[a]==a) return a;
return parent[a]=geP(parent[a]);
}
void unite(int a, int b){
a=geP(a);
b=geP(b);
if(a==b) return;
if(sz[a]<sz[b]){
swap(a,b);
}
sz[a]+=sz[b];
parent[b]=a;
}
bool same(int a, int b){
a=geP(a);
b=geP(b);
return (a==b);
}
void dfs1(int x){
if(visited[x]==1) return;
visited[x]=1;
for (auto u : neigh[x]) dfs1(u);
topo.push_back(x);
}
void dfs2(int x){
if(visited[x]==2) return;
visited[x]=2;
for (auto u : neighu[x]) {
if(visited[u]==2) continue;
unite(u,x);
unt=true;
dfs2(u);
}
}
std::vector<signed> find_reachable(std::vector<signed> _r, std::vector<signed> u, std::vector<signed> v, std::vector<signed> c) {
vector<int> r(sz(_r));
int n=sz(r);
for (int i = 0; i < n; i++)
{
r[i]=_r[i];
}
std::vector<signed> ans(n, 1);
neigh.resize(n);
neighu.resize(n);
for (int i = 0; i < sz(r); i++) r[i]=(1<<r[i]);
sz.resize(n,1);
parent.resize(n);
visited.resize(n);
topo.resize(n);
for (int i = 0; i < n; i++) parent[i]=i;
for (int i = 0; i < n; i++) sz[i]=1;
unt=true;
while(unt){
unt=false;
topo.clear();
for (int i = 0; i < n; i++) {
neigh[i].clear();
neighu[i].clear();
visited[i]=0;
r[geP(i)]|=r[i];
}
for (int i = 0; i < sz(u); i++)
{
if(same(geP(u[i]),geP(v[i]))) continue;
if(r[geP(u[i])]&(1<<c[i])){
neigh[geP(u[i])].push_back(geP(v[i]));
neighu[geP(v[i])].push_back(geP(u[i]));
}
if(r[geP(v[i])]&(1<<c[i])){
neigh[geP(v[i])].push_back(geP(u[i]));
neighu[geP(u[i])].push_back(geP(v[i]));
}
}
for (int i = 0; i < n; i++) dfs1(geP(i));
for (int i = 0; i < n; i++){
dfs2(geP(topo[(n-1)-i]));
}
k++;
}
int mn=1e9;
for (int i = 0; i < n; i++){
if(sz(neigh[geP(i)])==0) mn=min(sz[geP(i)],mn);
}
for (int i = 0; i < n; i++){
ans[i]=(mn==sz[geP(i)]&&sz(neigh[geP(i)])==0);
}
return ans;
}