제출 #768906

#제출 시각아이디문제언어결과실행 시간메모리
768906PurpleCrayon열쇠 (IOI21_keys)C++17
67 / 100
3057 ms178516 KiB
#include <bits/stdc++.h> using namespace std; #define sz(v) int(v.size()) #define ar array typedef long long ll; const int N = 3e5+10, MOD = 1e9+7; struct DSU { vector<int> par, sz; DSU(int n): par(n) { iota(par.begin(), par.end(), 0); sz.assign(n, 1); } int find_set(int v) { return v == par[v] ? v : par[v] = find_set(par[v]); } bool union_sets(int a, int b) { if ((a = find_set(a)) == (b = find_set(b))) return false; if (sz[a] < sz[b]) swap(a, b); par[b] = a, sz[a] += sz[b], sz[b] = 0; return true; } }; int n, m, my_out[N]; int par[N]; vector<int> st[N]; set<int> has[N]; map<int, vector<int>> by_col[N]; set<int> both[N]; vector<ar<int, 2>> adj[N]; void merge(int a, int b) { a = par[a], b = par[b]; if (a == b) return; if (sz(st[a]) < sz(st[b])) swap(a, b); for (int x : st[b]) { st[a].push_back(x); par[x] = a; } st[b].clear(); for (int x : has[b]) { has[a].insert(x); if (sz(by_col[a][x])) { both[a].insert(x); } } has[b].clear(); for (auto [x, v] : by_col[b]) { if (!sz(v)) continue; vector<int>& base = by_col[a][x]; for (int y : v) { base.push_back(y); } if (has[a].count(x)) { both[a].insert(x); } } by_col[b].clear(); both[b].clear(); } int get_out(int c) { c = par[c]; for (int x : has[c]) if (by_col[c].count(x) && sz(by_col[c][x])) { both[c].insert(x); } int ans = -1; vector<int> done; for (int x : both[c]) { vector<int>& v = by_col[c][x]; while (sz(v)) { if (par[v.back()] == c) { v.pop_back(); } else { ans = par[v.back()]; goto found; } } done.push_back(x); } found: for (int x : done) both[c].erase(x); return ans; } vector<int> find_reachable(vector<int> r, vector<int> u, vector<int> v, vector<int> c) { n = sz(r), m = sz(u); memset(my_out, -1, sizeof(my_out)); for (int i = 0; i < n; i++) { par[i] = i; st[i].push_back(i); has[i].insert(r[i]); } 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++) { for (auto [nxt, w] : adj[i]) { by_col[i][w].push_back(nxt); } for (int x : has[i]) if (sz(by_col[x])) { both[i].insert(x); } } DSU d(n); for (int root = 0; root < n; root++) { my_out[par[root]] = get_out(root); while (my_out[par[root]] != -1) { if (d.union_sets(root, my_out[par[root]])) { break; } else { vector<int> use{par[my_out[par[root]]]}; while (use.back() != par[root]) { use.push_back(par[my_out[use.back()]]); } use.pop_back(); for (int x : use) { merge(x, root); } my_out[par[root]] = get_out(root); } } } int best = MOD; for (int i = 0; i < n; i++) { int c = par[i]; if (my_out[c] == -1) { best = min(best, sz(st[c])); } } vector<int> ans(n); for (int i = 0; i < n; i++) { int c = par[i]; if (my_out[c] == -1 && sz(st[c]) == best) { ans[i] = 1; } } 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...