Submission #831392

#TimeUsernameProblemLanguageResultExecution timeMemory
831392Minindu206Keys (IOI21_keys)C++17
9 / 100
3059 ms28656 KiB
#include "keys.h" #include <bits/stdc++.h> using namespace std; vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) { int n = r.size(), m = u.size(), ans = INT_MAX; vector<pair<int, int>> adj[n]; vector<int> p(n), nrooms(n, 0); for (int i = 0; i < m; i++) { adj[u[i]].push_back({v[i], c[i]}); adj[v[i]].push_back({u[i], c[i]}); } for (int i = 0; i < n; i++) { vector<int> key(n, 0), vis(n, 0); vector<int> lst[n]; queue<int> q; q.push(i); key[r[i]] = 1; vis[i] = 1; while (!q.empty()) { int node = q.front(); q.pop(); vector<int> nkeys; for (auto pi : adj[node]) { if (!vis[pi.first]) { if (key[pi.second]) { vis[pi.first] = 1; q.push(pi.first); if (key[r[pi.second]] == 0) { key[r[pi.second]] = 1; nkeys.push_back(pi.second); } } else lst[pi.second].push_back(pi.first); } } for (auto k : nkeys) { for (auto nd : lst[k]) { if (!vis[nd]) { q.push(nd); key[r[nd]] = 1; vis[nd] = 1; } } lst[k].clear(); } } for (int j = 0; j < n; j++) nrooms[i] += vis[j]; ans = min(ans, nrooms[i]); } for (int i = 0; i < n; i++) p[i] = (nrooms[i] == ans); return p; }
#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...