| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 752503 | 1bin | 열쇠 (IOI21_keys) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 3e5 + 5;
int n, m, par[NMAX], dfsn[NMAX], fin[NMAX], sz[NMAX], bad[NMAX], t, from[NMAX];
vector<int> E[NMAX];
set<int> K[NMAX];
map<int, vector<int>> mp[NMAX];
int find(int x){return par[x] == -1 ? x : par[x] = find(par[x]);}
void Union(int a, int b){
for(auto& k : K[a]){
for(int& y : mp[b][k]) E[b].emplace_back(y);
mp[b].erase(k);
}
for(auto& k : K[b]){
for(int& y : mp[a][k]) E[a].emplace_back(y);
mp[a].erase(k);
}
if(K[a].size() < K[b].size()) swap(K[a], K[b]);
for(auto& k : K[b]) K[a].emplace(k);
K[b].clear();
if(E[a].size() < E[b].size()) swap(E[a], E[b]);
for(auto& e : E[b]) E[a].emplace_back(e);
E[b].clear();
if(mp[a].size() < mp[b].size()) swap(mp[a], mp[b]);
for(auto& [x, v] : mp[b]){
for(int& y : v) mp[a][x].emplace_back(y);
}
sz[a] += sz[b];
par[b] = a;
bad[a] |= bad[b];
return;
}
void dfs(int x){
dfsn[x] = ++t;
while(E[x].size()){
x = find(x);
int nx = find(E[x].back()); E[x].pop_back();
if(x == nx) continue;
if(!dfsn[nx]){
from[nx] = x;
dfs(nx);
}
else if(!fin[nx]){
for(int i = x; i != nx; i = from[i]) Union(nx, i);
}
if(find(nx) != find(x)) bad[x] = 1;
}
fin[x] = 1;
return;
}
vector<int> find_reachable(vector<int>r, vector<int> u, vector<int> v, vector<int> c){
n = r.size(); m = u.size();
auto add_edge = [&](int& a, int& b, int& c){
if(r[a] == c) E[a].emplace_back(b);
else mp[a][c].emplace_back(b);
};
for(int i = 0; i < m; i++) add_edge(u[i], v[i], c[i]);
memset(par, -1, sizeof(par));
queue<int> q;
t = n;
for(int i = 0; i < n; i++) sz[i] = 1, K[i].emplace(r[i]);
for(int i = 0; i < n; i++)
if(!dfsn[i]) dfs(i);
vector<int> res(n, 0);
int mn = n + 1;
for(int i = 0; i < n; i++) if(!bad[i]) mn = min(mn, sz[find(i)]);
for(int i = 0; i < n; i++) if(!bad[i] && sz[find(i)] == mn) res[i] = 1;
return res;
}
int main(void){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m;
cin >> n >> m;
vector<int> r(n), u(m), v(m), c(m);
for(auto& i : r) cin >> i;
for(auto& i : u) cin >> i;
for(auto& i : v) cin >> i;
for(auto& i : c) cin >> i;
vector<int> res = find_reachable(r, u, v, c);
for(int i = 0; i < n; i++) cout << res[i] << ' ';
return 0;
}
/*
test1
4 5
0 0 1 2
0 0 1 1 3
1 2 2 3 1
0 0 1 0 2
*/