Submission #1202636

#TimeUsernameProblemLanguageResultExecution timeMemory
1202636LucaLucaMKeys (IOI21_keys)C++20
37 / 100
3095 ms23880 KiB
#include <vector> #include <iostream> #include <algorithm> #include <cassert> #include <queue> 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<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]}); } std::vector<int> answer(n, n + 1); auto explore = [&](int start) { // un din asta am voie sa fac in O(n) std::queue<int> reach; // nu cred ca e neaparat sa fac bfs dar trebuie sa resetez niste chestii la final si atunci cand fac bfs pot doar sa dau break si se amortizeaza sau ceva reach.push(start); vis[start] = true; std::vector<int> visited; bool early = false; while (!reach.empty()) { int u = reach.front(); visited.push_back(u); reach.pop(); if (explored[start]) { // despre asta vorbeam mai sus early = true; assert(false); break; } int key = r[u]; for (const auto &[v, t] : g[u]) { if (!vis[v]) { if (haveKey[t]) { reach.push(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(u); } } } if (!early) { answer[start] = (int) visited.size(); } for (int i = 0; i < n; i++) { vis[i] = false; haveKey[i] = false; unlock[i].clear(); } // for (int u : visited) { // vis[u] = false; // haveKey[r[u]] = false; // unlock[r[u]].clear(); // } explored[start] = true; }; int mini = n + 1; for (int i = 0; i < n; i++) { explore(i); } for (int i = 0; i < n; 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...