Submission #1240449

#TimeUsernameProblemLanguageResultExecution timeMemory
1240449trimkusKeys (IOI21_keys)C++20
9 / 100
3094 ms2162688 KiB
#include "keys.h" #include <bits/stdc++.h> using namespace std; 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(); vector<vector<array<int, 2>>> adj(N); for (int i = 0; i < (int)u.size(); ++i) { adj[u[i]].push_back({v[i], c[i]}); adj[v[i]].push_back({u[i], c[i]}); } vector<int> cnt(N); for (int i = 0; i < N; ++i) { vector<vector<int>> vis(N, vector<int>(N)); vector<int> seen(N); queue<pair<int, unordered_set<int>>> q; q.push({i, {r[i]}}); vis[i][r[i]] = 1; while (q.size()) { int v = q.front().first; unordered_set<int> key = q.front().second; q.pop(); for (auto& [u, C] : adj[v]) { if (!key.count(C)) continue; bool ok = false; for (int j = 0; j < N; ++j) { if (vis[u][j]) continue; if (key.count(j)) { ok = true; continue;; } } if (!ok) continue; for (auto& g : key) { vis[u][g] = 1; } seen[u] = 1; auto nkey = key; nkey.insert(r[u]); q.push({u, nkey}); } } 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...