| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 835027 | jmyszka2007 | 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 <fstream>using namespace std;template<class A, class B>ostream& operator<<(ostream& o, const pair<A, B>& p) {return o << '(' << p.first << ", " << p.second << ')';}template<size_t Index = 0, typename... Types>ostream& printTupleElements(ostream& o, const tuple<Types...>& t) {if constexpr (Index < sizeof...(Types)){if(Index > 0){o << ", ";}o << get<Index>(t);printTupleElements<Index + 1>(o, t);}return o;}template<typename... Types>ostream& operator<<(ostream& o, const tuple<Types...>& t){o << "(";printTupleElements(o, t);return o << ")";}template<class T>auto operator<<(ostream& o, const T& x) -> decltype(x.end(), o){o << '{';bool first = true;for (const auto& e : x){if (!first){o << ", ";}o << e;first = false;} return o << '}';}//#define DEBUG#ifdef DEBUG#define fastio()#define debug(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n'#define check(x) if (!(x)) { cerr << "Check failed: " << #x << " in line " << __LINE__ << endl; exit(1); }#else#define fastio() ios_base::sync_with_stdio(0); cin.tie(0);#define debug(...)#define check(x) #endiftypedef long long ll;#define pi pair<int, int>#define pl pair<ll, ll>#define st first#define nd second#define vi vector<int>#define vll vector<ll>#define eb emplace_back#define all(x) (x).begin(), (x).end()#define sz(x) (int)(x).size()constexpr int LIM = 3e5;vi g[LIM + 10];vi go[LIM + 10];bool vis[LIM + 10];int nr[LIM + 10];unordered_map<int, int>czy[LIM + 10];vi post, sp;void dfs(int v) { vis[v] = 1; for(auto x : g[v]) { if(!vis[x]) { dfs(x); } } post.eb(v);}void dfs2(int v) { vis[v] = 1; sp.eb(v); for(auto x : go[v]) { if(!vis[x]) { dfs2(x); } }}void solve() { //ifstream cin("nazwa.in"); //ofstream cout("nazwa.out"); int n, m; cin >> n >> m; vector<vi>kt(n); vi tab(n); for(int i = 0; i < n; i++) { int x; cin >> x; tab[i] = x; czy[i][x] = 1; kt[i].eb(i); nr[i] = i; } vector<tuple<int, int, int> >kr; int mx = 0; for(int i = 1; i <= m; i++) { int a, b, c; cin >> a >> b >> c; kr.eb(a, b, c); mx = max(mx, c); } vector<vi>popkt = kt; while(1) { debug(kt); for(int i = 0; i < sz(kt); i++) { debug(i); debug(czy[i]); } for(auto &[a, b, c] : kr) { if(nr[a] != nr[b]) { if(czy[nr[a]][c]) { debug(nr[a], nr[b], c); g[nr[a]].eb(nr[b]); } if(czy[nr[b]][c]) { debug(nr[b], nr[a], c); g[nr[b]].eb(nr[a]); } } } for(int i = 0; i < sz(kt); i++) { if(!vis[i]) { dfs(i); } } for(int i = 0; i < sz(kt); i++) { for(auto x : g[i]) { go[x].eb(i); } vis[i] = 0; } reverse(all(post)); int k = 0; vector<vi>newkt; for(auto x : post) { if(!vis[x]) { dfs2(x); vi tmp; for(auto y : sp) { for(auto z : kt[y]) { nr[z] = k; tmp.eb(z); } } k++; sp.clear(); newkt.eb(tmp); } } for(int i = 0; i < sz(kt); i++) { g[i].clear(); go[i].clear(); vis[i] = 0; } kt = newkt; for(int i = 0; i < sz(kt); i++) { czy[i].clear(); for(auto x : kt[i]) { czy[i][tab[x]] = 1; } } post.clear(); vector<vi> nkt = kt; sort(all(nkt)); if(nkt == popkt) { break; } popkt = nkt; } vi dp(sz(kt)); vector<vi> ng(sz(kt)); for(auto &[a, b, c] : kr) { if(nr[a] == nr[b]) { continue; } if(czy[nr[a]][c]) { ng[nr[a]].eb(nr[b]); } if(czy[nr[b]][c]) { ng[nr[b]].eb(nr[a]); } } int mn = 1e9; for(int i = sz(kt) - 1; i >= 0; i--) { dp[i] = sz(kt[i]); for(auto x : ng[i]) { dp[i] += dp[x]; } mn = min(mn, dp[i]); } vi res(n, 0); for(int i = 0; i < sz(kt); i++) { if(dp[i] == mn) { for(auto x : kt[i]) { res[x] = 1; } } } for(auto x : res) { cout << x << ' '; } cout << '\n';}int main() { fastio(); int t; //cin >> t; t = 1; while(t--) { solve(); }}