Submission #1202622

#TimeUsernameProblemLanguageResultExecution timeMemory
1202622LucaLucaMKeys (IOI21_keys)C++20
37 / 100
3095 ms23828 KiB
#include <vector> #include <iostream> #include <algorithm> #include <cassert> std::vector<int> find_reachable(std::vector<int> r, std::vector<int> u, std::vector<int> v, std::vector<int> c) { int n = (int) r.size(); std::vector<int> ans(r.size(), 1); std::vector<bool> haveKey(n, false); std::vector<std::vector<int>> unlock(n); std::vector<bool> explored(n, false); std::vector<bool> vis(n, false); int m = (int) u.size(); std::vector<std::vector<std::pair<int, int>>> g(n); for (int i = 0; i < m; i++) { g[u[i]].push_back({v[i], c[i]}); g[v[i]].push_back({u[i], c[i]}); } auto explore = [&](int start) { // un din asta am voie sa fac in O(n) for (int i = 0; i < n; i++) { haveKey[i] = false; vis[i] = false; unlock[i].clear(); } std::vector<int> reach; reach.push_back(start); vis[start] = true; while (!reach.empty()) { int u = reach.back(); reach.pop_back(); int key = r[u]; for (const auto &[v, t] : g[u]) { if (!vis[v]) { if (haveKey[t]) { reach.push_back(v); vis[v] = true; } else { unlock[t].push_back(v); } } } if (haveKey[key]) { continue; } haveKey[key] = true; for (const auto &u : unlock[key]) { if (!vis[u]) { vis[u] = true; reach.push_back(u); } } } return std::count(vis.begin(), vis.end(), true); }; std::vector<int> answer(n); int mini = n + 1; for (int i = 0; i < n; i++) { answer[i] = explore(i); mini = std::min(mini, answer[i]); } std::vector<int> ret(n); for (int i = 0; i < n; i++) { ret[i] = (answer[i] == mini); } return ret; }
#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...