| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 811252 | penguinman | 열쇠 (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>
using std::cin;
using std::cout;
using std::vector;
using std::string;
using ll = int;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
using std::endl;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()
constexpr ll inf = (1ll<<60);
struct directed_graph{
ll N;
vii edge;
vii revedge;
vi par;
vii member;
directed_graph(ll n): N(n){
edge.resize(N);
revedge.resize(N);
}
void add_edge(ll u, ll v){
edge[u].pb(v);
revedge[v].pb(u);
}
vi ord, rev;
vector<bool> flag;
void dfs1(ll now){
flag[now] = true;
for(auto next: edge[now]){
if(!flag[next]) dfs1(next);
}
ord.pb(now);
}
void dfs2(ll now, ll root){
rev[now] = root;
for(auto next: revedge[now]){
if(rev[next] == -1) dfs2(next, root);
}
}
vi SCC(){
flag.resize(N);
rev.resize(N,-1);
ll cnt = 0;
rep(i,0,N){
if(!flag[i]) dfs1(i);
}
reverse(all(ord));
for(auto i: ord){
if(rev[i] == -1) dfs2(i, i);
}
return rev;
}
};
std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) {
ll N = r.size();
vii edge(N), key(N);
rep(i,0,u.size()){
edge[u[i]].pb(v[i]);
edge[v[i]].pb(u[i]);
key[u[i]].pb(c[i]);
key[v[i]].pb(c[i]);
}
vi par(N);
ll Rmax = *max_element(all(r))+1;
vector<vector<bool>> obtained(N,vector<bool>(Rmax));
rep(i,0,N){
par[i] = i;
obtained[i][r[i]] = true;
}
while(true){
directed_graph G(N);
rep(i,0,N){
rep(j,0,edge[i].size()){
ll next = edge[i][j];
if(par[next] == par[i]) continue;
if(!obtained[par[i]][key[i][j]]) continue;
G.add_edge(par[i],par[next]);
}
}
{
vi v;
vector<bool> flag(N);
rep(i,0,N){
if(par[i] == i){
if(G.edge[i].empty()){
v.pb(i);
flag[i] = true;
}
}
}
if(!v.empty()){
vi member(N);
rep(i,0,N){
if(flag[par[i]]) member[par[i]]++;
}
ll min = inf;
rep(i,0,N){
if(member[i]) min = std::min(min, member[i]);
}
vector<int> ans(N);
rep(i,0,N){
if(member[par[i]] == min) ans[i] = 1;
}
return ans;
}
}
par = G.SCC();
rep(i,0,N) obtained[par[i]][r[i]] = true;
}
}
int main() {
int n, m;
assert(2 == scanf("%d%d", &n, &m));
std::vector<int> r(n), u(m), v(m), c(m);
for(int i=0; i<n; i++) {
assert(1 == scanf("%d", &r[i]));
}
for(int i=0; i<m; i++) {
assert(3 == scanf("%d %d %d", &u[i], &v[i], &c[i]));
}
fclose(stdin);
std::vector<int> ans = find_reachable(r, u, v, c);
for (int i = 0; i < (int) ans.size(); ++i) {
if(i) putchar(' ');
putchar(ans[i]+'0');
}
printf("\n");
return 0;
}