제출 #615584

#제출 시각아이디문제언어결과실행 시간메모리
615584SeDunion열쇠 (IOI21_keys)C++17
37 / 100
3051 ms367024 KiB
#include "keys.h" #include <iostream> #include <vector> #include <set> #define cerr if(false)cerr using namespace std; using vi = vector<int>; const int N = 300'005; set<int>keys[N]; set<pair<int,int>>maybe[N]; vector<int>ac[N]; int tree[N]; int gtree(int x) { if (x == tree[x]) return x; return tree[x] = gtree(tree[x]); } int cc[N]; int gcc(int x) { if (x == cc[x]) return x; return cc[x] = gcc(cc[x]); } int par[N]; void add_edge(int x, int y) { cerr << "\t" << x << " -> " << y << " edge\n"; tree[x] = y; par[x] = y; } void unite(int x, int y) { x = gcc(x), y = gcc(y); if (x == y) return; if (keys[x].size() + maybe[x].size() + ac[x].size() > keys[y].size() + maybe[y].size() + ac[y].size()) swap(x, y); cc[x] = y; for (auto u : ac[x]) ac[y].emplace_back(u); ac[x].clear(); for (auto u : keys[x]) { auto it = maybe[y].lower_bound({u, -1}); while (it != maybe[y].end() && it->first == u) { ac[y].emplace_back(it->second); ++it; } keys[y].insert(u); } keys[x].clear(); for (auto it : maybe[x]) { if (keys[y].count(it.first)) ac[y].emplace_back(it.second); else maybe[y].insert(it); } maybe[x].clear(); } void collapse(int x, int y) { cerr << "\t" << x << " -> " << y << " collapse\n"; while (x != y) { unite(x, y); y = par[y]; } int a = gtree(gcc(x)); int b = gcc(x); tree[b] = b; tree[a] = b; cerr << "\ttree " << a << " -> " << b << endl; } void push(int v) { v = gcc(v); v = gtree(v); while (ac[v].size()) { int t = ac[v].back(); ac[v].pop_back(); t = gcc(t); int tv = gtree(v); int tt = gtree(t); if (tv != tt) { add_edge(v, tt); push(t); return; } // cycle collapse(v, t); v = gcc(v); v = gtree(v); push(v); return; } } vi norm(int n, vi a) { vi r(n); for (int i : a) r[i] = 1; return r; } vi find_reachable(vi r, vi u, vi v, vi c) { int n = r.size(); int m = u.size(); vi ans; for (int i = 0 ; i < n ; ++ i) { tree[i] = cc[i] = par[i] = i; } for (int i = 0 ; i < m ; ++ i) { maybe[u[i]].insert({c[i], v[i]}); maybe[v[i]].insert({c[i], u[i]}); } for (int i = 0 ; i < n ; ++ i) { keys[i].insert(r[i]); auto it = maybe[i].lower_bound({r[i], -1}); while (it != maybe[i].end() && it->first == r[i]) ac[i].emplace_back(it->second), it++; if (ac[i].empty()) ans.emplace_back(i); } if (ans.size()) return norm(n, ans); for (int i = 0 ; i < n ; ++ i) { push(i); } for (int i = 0 ; i < n ; ++ i) { cerr << gcc(i) << " "; } cerr << endl; vi cnt(n); for (int i = 0 ; i < n ; ++ i) { int x = gcc(i); if (x == gtree(x)) cnt[x]++; else cnt[x] = N; } int mn = N; for (int i = 0 ; i < n ; ++ i) { int x = gcc(i); mn = min(mn, cnt[x]); } for (int i = 0 ; i < n ; ++ i) { cerr << gtree(gcc(i)) << " "; } cerr << endl; for (int i = 0 ; i < n ; ++ i) { cerr << cnt[i] << " "; } cerr << endl; for (int i = 0 ; i < n ; ++ i) { int x = gcc(i); if (cnt[x] == mn) ans.emplace_back(i); } return norm(n, 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...