제출 #768899

#제출 시각아이디문제언어결과실행 시간메모리
768899PurpleCrayon열쇠 (IOI21_keys)C++17
37 / 100
3052 ms60632 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]; 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); } has[b].clear(); for (auto nxt : adj[b]) { adj[a].push_back(nxt); } adj[b].clear(); } int get_out(int c) { c = par[c]; for (auto [nxt, w] : adj[c]) { if (par[nxt] != c && has[c].count(w)) { return par[nxt]; } } return -1; } 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]}); } 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...