Submission #593755

#TimeUsernameProblemLanguageResultExecution timeMemory
593755MadokaMagicaFanKeys (IOI21_keys)C++17
0 / 100
107 ms211596 KiB
#include "bits/stdc++.h" using namespace std; using ll = long long; const ll inf = 1e9; const int md1 = 1e9+7; const int md2 = 998244353; #define sz(v) ((int)(v).size()) #define pb push_back #define pry cout << "YES\n" #define prn cout << "NO\n" #define endl '\n' #define fst first #define scn second /* #define ONPC */ using vi = vector<int>; using pi = array<int,2>; const int N = 3e5; int st[N+1]; int us[N]; int p[N+1]; int ch[N+1]; int d[N+1]; /* deque<int> q[N]; */ /* set<int> s[N]; */ int s[N]; vi adj[N][30]; int getp(int x) { return p[x] = (x == p[x]) ? x : getp(p[x]); } int dfs(int x) { if (st[x]&1) return p[x]; st[x] |= 1; int lc = 1, u; while (lc) { lc = 0; for (int i = 0; i < 30; ++i) { if ((s[x]>>i)&1) { while (sz(adj[x][i])) { u = adj[x][i].back(); u = getp(u); adj[x][i].pop_back(); if (!(st[u]&1)) { d[u] = d[x]+1; dfs(u); ch[x] += ch[u]; if (d[getp(x)] > d[getp(u)]) { p[x] = getp(u); i = 31; lc = 0; break; } lc = 1; } else if (st[u]&2) { p[x] = N; i = 31; lc = 0; break; } else { p[x] = getp(u); i = 31; lc = 0; break; } } } } } st[x] |= 2; /* Check if useless */ if (p[x] == N) return p[x]; /* Check if has bigger parrent */ if (getp(x) != x) { /* Push all values */ int u = getp(x); s[u] |= s[x]; for (int i = 0; i < 30; ++i) { if (sz(adj[x][i]) > sz(adj[u][i])) swap(adj[x][i], adj[u][i]); while (sz(adj[x][i])) { adj[u][i].pb(adj[x][i].back()); adj[x][i].pop_back(); } } } return p[x]; } vi find_reachable(vi r, vi u, vi v, vi c) { vi ans; int n, m; n = sz(r); m = sz(u); p[N] = N; ch[N] = N+1; d[N] = -1; for (int i = 0; i < n; ++i) { p[i] = i; ch[i] = 1; d[i] = 0; s[i] = 1<<(r[i]); /* s[i].insert(r[i]); */ } for (int i = 0; i < m; ++i) { /* q[u[i]].pb(i); */ assert(c[i] < 30); adj[u[i]][c[i]].pb(v[i]); adj[v[i]][c[i]].pb(u[i]); } for (int i = 0; i < n; ++i) { if (st[i] == 0) dfs(i); } int mnv = N+2; for (int i = 0; i < n; ++i) { mnv = min(mnv,ch[getp(i)]); } for (int i = 0; i < n; ++i) { if (ch[getp(i)] == mnv) ans.pb(i); } return ans; } #ifdef INTER #endif #ifdef ONPC void solve() { int _n, _m; cin >> _n >> _m; cout << _n << ' ' << _m << endl; vector<int> r(_n); for (int i = 0; i < _n; ++i) cin >> r[i]; vector<int> u(_m), v(_m), c(_m); for (int i = 0; i < _m; ++i) cin >> u[i] >> v[i] >> c[i]; vi ans = find_reachable(r, u, v, c); for (auto u : ans) { cout << u << ' '; } cout << endl; } int32_t main(int argc, char **argv) { if (argc >= 2) { freopen(argv[1], "r", stdin); } else ios_base::sync_with_stdio(0);cin.tie(0); int t = 1; /* cin >> t; */ while(t--) solve(); } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...