제출 #443463

#제출 시각아이디문제언어결과실행 시간메모리
443463mjhmjh1104열쇠 (IOI21_keys)C++17
37 / 100
3064 ms37104 KiB
#include "keys.h" #include <queue> #include <tuple> #include <vector> #include <utility> #include <algorithm> #include <functional> using namespace std; bool found[300006], visited[300006], visited_edge[300006]; vector<tuple<int, int, int>> adj[300006]; vector<pair<int, int>> lt[300006]; vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) { queue<int> q; function<void (int)> dfs = [&](int v) { for (auto &i: lt[r[v]]) if (!visited[i.second]) { visited[i.second] = true; q.push(i.second); if (!found[r[i.second]]) { found[r[i.second]] = true; dfs(i.second); } } }; int n = (int)r.size(), m = (int)c.size(); for (int i = 0; i < m; i++) { adj[u[i]].push_back({ v[i], c[i], i }); adj[v[i]].push_back({ u[i], c[i], i }); } vector<int> ans(n), p; for (int i = 0; i < n; i++) { fill(found, found + n, false); fill(visited, visited + n, false); fill(visited_edge, visited_edge + m, false); for (int i = 0; i < n; i++) lt[i].clear(); visited[i] = true; found[r[i]] = true; while (!q.empty()) q.pop(); q.push(i); while (!q.empty()) { int t = q.front(); q.pop(); for (auto &i: adj[t]) if (!visited_edge[get<2>(i)]) { auto [ v, c, j ] = i; visited_edge[j] = true; if (found[c]) { if (!visited[v]) { visited[v] = true; q.push(v); if (!found[r[v]]) { found[r[v]] = true; dfs(v); } } } else lt[c].push_back({ j, v }); } } int cnt = 0; for (int i = 0; i < n; i++) if (visited[i]) cnt++; p.push_back(cnt); } int globalMin = *min_element(p.begin(), p.end()); for (int i = 0; i < n; i++) ans[i] = (globalMin == p[i]); return ans; }
#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...