제출 #495405

#제출 시각아이디문제언어결과실행 시간메모리
495405Giantpizzahead열쇠 (IOI21_keys)C++17
0 / 100
63 ms80140 KiB
#include <bits/stdc++.h> #define rep(i, a, b) for (int i = (a); i < (b); i++) #define sz(x) ((int) x.size()) #define all(x) x.begin(), x.end() #define debug if (false) cerr using namespace std; using ll = long long; const int MAXN = 6e5+10; int N, M; vector<int> R, ans, ds; unordered_map<int, vector<int>> adj[MAXN]; unordered_set<int> keys[MAXN]; vector<int> toVisit[MAXN]; vector<int> vis, finalNodes; vector<bool> isLeaf; void init() { rep(i, 0, N) ds[i] = -1; } int find(int x) { if (ds[x] < 0) return x; int r = find(ds[x]); ds[x] = r; return r; } void addVisit(unordered_map<int, vector<int>>& a, unordered_set<int>& k, vector<int>& v) { vector<int> temp; if (sz(a) < sz(k)) { // Iterate through edges for (auto& r : a) { if (k.count(r.first)) { // Key and edges match temp.push_back(r.first); for (int e : r.second) { v.push_back(find(e)); } } } } else { // Iterate through keys for (auto& r : k) { if (a.count(r)) { // Key and edges match temp.push_back(r); for (int e : a[r]) { v.push_back(find(e)); } } } } for (int r : temp) a.erase(r); } int merge(int a, int b) { a = find(a), b = find(b); if (a == b) return a; else if (ds[a] < ds[b]) swap(a, b); auto& adjA = adj[a]; auto& adjB = adj[b]; auto& keysA = keys[a]; auto& keysB = keys[b]; auto& toVisitA = toVisit[a]; auto& toVisitB = toVisit[b]; // Add to toVisit addVisit(adjA, keysB, toVisitA); addVisit(adjB, keysA, toVisitB); // Merge adj, keys, and toVisit if (sz(adjA) < sz(adjB)) { adjB.insert(all(adjA)); // adj[b] = adjB; } else { adjA.insert(all(adjB)); swap(adj[a], adj[b]); } if (sz(keysA) < sz(keysB)) { keysB.insert(all(keysA)); // keys[b] = keysB; } else { keysA.insert(all(keysB)); swap(keys[a], keys[b]); } if (sz(toVisitA) < sz(toVisitB)) { toVisitB.insert(toVisitB.end(), all(toVisitA)); // toVisit[b] = toVisitB; } else { toVisitA.insert(toVisitA.end(), all(toVisitB)); swap(toVisitA, toVisitB); } // Merge a into b vis[b] = 1; isLeaf[b] = true; ds[b] += ds[a]; ds[a] = b; return b; } stack<int> currNodes; void dfs(int n) { n = find(n); if (vis[n] == 2) return; /* debug << "dfs(" << n << ")" << endl; rep(i, 0, N) debug << ds[i] << " \n"[i==N-1]; rep(i, 0, N) { debug << i << ": "; for (int k : keys[i]) debug << k << " "; for (auto r : adj[i]) { debug << "(" << r.first << " |"; for (int e : r.second) debug << " " << e; debug << ") "; } debug << "/ "; for (int e : toVisit[i]) debug << e << " "; debug << endl; } debug << endl; */ vis[n] = 1; currNodes.push(n); vector<int> visited; while (!toVisit[n].empty()) { int e = find(toVisit[n].back()); toVisit[n].pop_back(); visited.push_back(e); // debug << "vis " << e << " from " << n << endl; if (e == n) continue; else if (vis[e] == 0) { // Fresh node; start there dfs(e); } else if (vis[e] == 1) { // Cycle; merge all nodes in cycle int newN = n; while (find(currNodes.top()) != e) { newN = merge(find(currNodes.top()), n); currNodes.pop(); } newN = merge(find(currNodes.top()), n); currNodes.pop(); dfs(newN); n = find(n); break; } else if (vis[e] == 2) { // Would visit } n = find(n); } for (int e : visited) if (n != find(e)) isLeaf[n] = false; vis[n] = 2; } void solve() { // Generate initial toVisit rep(n, 0, N) { keys[n].insert(R[n]); if (!adj[n].count(R[n])) continue; for (int e : adj[n][R[n]]) { toVisit[n].push_back(e); } adj[n].erase(R[n]); } vector<int> visOrder(N); rep(i, 0, N) visOrder[i] = i; // srand(time(NULL)); // random_shuffle(all(visOrder)); rep(i, 0, N) { int n = visOrder[i]; if (vis[find(n)] == 0) dfs(find(n)); } int minSize = MAXN; unordered_set<int> minRoots; rep(n, 0, N) { if (find(n) != n || !isLeaf[n]) continue; int s = -ds[n]; if (s < minSize) { minRoots.clear(); minSize = s; } if (s <= minSize) minRoots.insert(n); } rep(n, 0, N) { ans[n] = (minRoots.count(find(n)) != 0); } } vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) { R.clear(); ans.clear(); ds.clear(); vis.clear(); finalNodes.clear(); isLeaf.clear(); rep(i, 0, N) { adj[i].clear(); keys[i].clear(); toVisit[i].clear(); } N = sz(r), M = sz(u); R = r; ans.resize(N); vis.resize(N); isLeaf.resize(N, true); ds.resize(N); init(); rep(i, 0, M) { adj[u[i]][c[i]].push_back(v[i]); adj[v[i]][c[i]].push_back(u[i]); } solve(); return ans; } /* int main() { ios::sync_with_stdio(0); cin.tie(0); vector<int> r{0,1,1,2}; vector<int> u{0,0,1,1,3}; vector<int> v{1,2,2,3,1}; vector<int> c{0,0,1,0,2}; vector<int> ans = find_reachable(r,u,v,c); rep(i, 0, sz(ans)) cout << ans[i] << " \n"[i==sz(ans)-1]; return 0; } */
#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...