Submission #1240477

#TimeUsernameProblemLanguageResultExecution timeMemory
1240477trimkusKeys (IOI21_keys)C++20
0 / 100
0 ms324 KiB
#include "keys.h" #include <bits/stdc++.h> using namespace std; struct DSU { vector<int> e; vector<unordered_set<int>> st; DSU(int n) { e = vector<int>(n, -1); st = vector<unordered_set<int>>(n); } int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } bool can_unite(int x, int r) { x = get(x); return st[x].count(r); } void unite(int x, int y) { x = get(x); y = get(y); if (x == y) return; if (e[x] > e[y]) swap(x, y); if (st[x].size() > st[y].size()) { swap(st[x], st[y]); } for (auto& u : st[y]) { st[x].insert(u); } e[x] += e[y]; st[y].clear(); e[y] = x; } }; std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) { int N = r.size(); int M = u.size(); vector<vector<array<int, 3>>> adj(N); for (int i = 0; i < (int)u.size(); ++i) { adj[u[i]].push_back({v[i], c[i], i}); adj[v[i]].push_back({u[i], c[i], i}); } vector<int> cnt(N); for (int i = 0; i < N; ++i) { vector<int> seen(N), inq(M); vector<int> now{i}; unordered_set<int> have; have.insert(r[i]); vector<array<int, 3>> toadd; while (true) { bool added = false; while (now.size() > 0) { int v = now.back(); now.pop_back(); for (auto& [u, c, idx] : adj[v]) { if (seen[u] || inq[idx]) continue; toadd.push_back({u, c, idx}); inq[idx] = true; added = true; } } sort(begin(toadd), end(toadd), [&](array<int, 3> x, array<int, 3> y) { if (!have.count(x[1])) return true; if (!have.count(y[1])) return false; return true; }); // for (auto& u : toadd) { // cout << have.count(u[1]) << " "; // } // cout << "\n"; while (toadd.size() > 0) { int c = toadd.back()[1]; int v = toadd.back()[0]; if (seen[v]) { toadd.pop_back(); continue;; } if (have.count(c)) { seen[v] = 1; now.push_back(v); have.insert(r[v]); toadd.pop_back(); } else { break; } } if (!added) break; } for (int j = 0; j < N; ++j) { cnt[i] += seen[j]; } } vector<int> res(N); int mn = *min_element(begin(cnt), end(cnt)); for (int i = 0; i < N; ++i) { if (mn == cnt[i]) { res[i] = 1; } } return res; }
#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...