| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 898806 | hazzle | Keys (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>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define all(m) (m).begin(), (m).end()
#define rall(m) (m).rbegin(), (m).rend()
#define vec vector
#define sz(a) (int) (a).size()
#define mpp make_pair
#define mtt make_tuple
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
typedef tuple <int, int, int> tui;
template <typename T>
using prq = priority_queue <T>;
template <typename T>
using pgq = priority_queue <T, vec <T>, greater <T>>;
template <typename T> bool umin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> bool umax(T &a, T b) { return a < b ? a = b, 1 : 0; }
inline int solve(){
int n, m;
cin >> n >> m;
vec <int> r(n);
for (auto &i: r) cin >> i, --i;
vec <vec <pii>> g(n);
int mx_c = 0;
for (int i = 0; i < m; ++i){
int u, v, c;
cin >> u >> v >> c, --u, --v, --c;
g[u].push_back({v, c});
g[v].push_back({u, c});
umax(mx_c, c);
}
auto calc = [&](int s){
unordered_map <int, bool> have(n), us(n);
unordered_map <int, vec <int>> qu(n);
vec <int> bfs = {s};
us[s] = 1;
for (int pt = 0; pt < sz(bfs); ++pt){
int u = bfs[pt];
have[r[u]] = 1;
for (auto &v: qu[r[u]]) if (!us[v]){
us[v] = 1;
bfs.push_back(v);
}
qu[r[u]].clear();
for (auto &[v, c]: g[u]) if (!us[v]){
if (have[c]){
us[v] = 1;
bfs.push_back(v);
}
else{
qu[c].push_back(v);
}
}
}
return sz(bfs);
};
if (max(n, m) <= 2000){
int mn = n + 42;
vec <int> f(n);
for (int s = 0; s < n; ++s){
umin(mn, f[s] = calc(s));
}
for (int i = 0; i < n; ++i){
cout << (f[i] == mn) << " ";
}
}
else if (mx_c < 30){
vec <int> msk(n);
for (int i = 0; i < n; ++i){
msk[i] = 1 << r[i];
}
auto sup = [&](int x, int y){
return x == (x | y);
};
vec <tui> bfs;
for (int u = 0; u < n; ++u){
for (auto &[v, c]: g[u]){
bfs.push_back({u, v, c});
}
}
for (int pt = 0; pt < sz(bfs); ++pt){
auto [u, v, c] = bfs[pt];
if (sup(msk[u], 1 << c) && !sup(msk[u], msk[v])){
msk[u] |= msk[v];
for (auto &[x, k]: g[u]){
bfs.push_back({u, x, k});
}
}
}
vec <vec <int>> gg(n), dd(n);
for (int u = 0; u < n; ++u){
for (auto &[v, c]: g[u]){
if (sup(msk[u], 1 << c)){
gg[u].push_back(v);
dd[v].push_back(u);
}
}
}
vec <bool> us(n);
vec <int> top;
auto dfs = [&](auto &&dfs, int u) -> void{
us[u] = 1;
for (auto &v: gg[u]){
if (!us[v]) dfs(dfs, v);
}
top.push_back(u);
};
for (int i = 0; i < n; ++i){
if (!us[i]) dfs(dfs, i);
}
reverse(all(top));
fill(all(us), 0);
vec <int> cmp(n);
int z = 0;
auto col = [&](auto &&col, int u) -> void{
us[u] = 1;
cmp[u] = z;
for (auto &v: dd[u]){
if (!us[v]) col(col, v);
}
};
for (auto &u: top) if (!us[u]){
col(col, u), ++z;
}
vec <int> deg(z);
for (int u = 0; u < n; ++u){
for (auto &v: gg[u]){
if (cmp[u] != cmp[v]){
++deg[cmp[u]];
}
}
}
vec <int> _f(z, 1e9), f(n, 1e9);
for (int i = 0; i < n; ++i){
if (_f[cmp[i]] == 1e9 && !deg[cmp[i]]){
_f[cmp[i]] = calc(i);
}
}
int mn = 1e9;
for (int i = 0; i < n; ++i){
umin(mn, f[i] = _f[cmp[i]]);
}
for (int i = 0; i < n; ++i){
cout << (f[i] == mn) << " ";
}
}
return 0;
}
inline void precalc(){}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tst = 1; //cin >> tst;
precalc();
while(tst--) solve();
return 0;
}