Submission #374934

#TimeUsernameProblemLanguageResultExecution timeMemory
374934valerikkCollapse (JOI18_collapse)C++17
100 / 100
8719 ms29804 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 7; int dsu[N], sz[N]; int comps; vector<int> g[N]; bool vis[N]; int added; void dfs(int v) { vis[v] = 1; for (int u : g[v]) { if (!vis[u]) { ++added; dfs(u); } } } int get(int v) { return dsu[v] == v ? v : dsu[v] = get(dsu[v]); } void unite(int v, int u) { v = get(v); u = get(u); if (v == u) return; --comps; if (sz[v] > sz[u]) swap(v, u); sz[u] += sz[v]; dsu[v] = u; } void init(int n) { for (int i = 0; i < n; ++i) { dsu[i] = i; sz[i] = 1; } comps = n; } vector<int> solve(int n, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p) { int c = t.size(), q = w.size(); for (int i = 0; i < c; ++i) { if (x[i] > y[i]) swap(x[i], y[i]); } vector<int> when(c, c), who(c, -1); map<pair<int, int>, int> lst; for (int i = 0; i < c; ++i) { if (t[i] == 0) { lst[{x[i], y[i]}] = i; } else { who[i] = lst[{x[i], y[i]}]; when[lst[{x[i], y[i]}]] = i; } } int sq = sqrt(c); vector<int> d(q, 0); for (int l = 0; l < c; l += sq) { int r = min(c, l + sq); vector<int> here; vector<vector<int>> by_y(n + 1), by_p(n + 1); for (int i = 0; i < l; ++i) { if (t[i] == 1) continue; if (when[i] >= r) { by_y[y[i]].push_back(i); } } for (int i = l; i < r; ++i) { if (t[i] == 0) here.push_back(i); else here.push_back(who[i]); } sort(here.begin(), here.end()); here.erase(unique(here.begin(), here.end()), here.end()); for (int i = 0; i < q; ++i) { if (w[i] >= l && w[i] < r) by_p[p[i]].push_back(i); } init(n); for (int i = 0; i <= n; ++i) { for (int id : by_p[i]) { d[id] = comps - n + i; vector<pair<int, int>> edges; for (int edge_id : here) { if (edge_id <= w[id] && w[id] < when[edge_id] && y[edge_id] < i) edges.push_back({get(x[edge_id]), get(y[edge_id])}); } for (auto [u, v] : edges) { g[u] = g[v] = {}; vis[u] = vis[v] = 0; } for (auto [u, v] : edges) { g[u].push_back(v); g[v].push_back(u); } added = 0; for (auto [u, v] : edges) { if (!vis[u]) dfs(u); if (!vis[v]) dfs(v); } d[id] -= added; } for (int edge_id : by_y[i]) unite(x[edge_id], y[edge_id]); } } return d; } vector<int> simulateCollapse(int n, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p) { int c = t.size(), q = w.size(); for (int i = 0; i < q; ++i) ++p[i]; auto d1 = solve(n, t, x, y, w, p); for (int i = 0; i < c; ++i) { x[i] = n - x[i] - 1; y[i] = n - y[i] - 1; } for (int i = 0; i < q; ++i) p[i] = n - p[i]; auto d2 = solve(n, t, x, y, w, p); vector<int> d(q); for (int i = 0; i < q; ++i) d[i] = d1[i] + d2[i]; return d; } #ifndef EVAL int main() { freopen("input.txt", "r", stdin); ios::sync_with_stdio(false); cin.tie(0); int n, c, q; cin >> n >> c >> q; vector<int> t(c), x(c), y(c); for (int i = 0; i < c; ++i) cin >> t[i] >> x[i] >> y[i]; vector<int> w(q), p(q); for (int i = 0; i < q; ++i) cin >> w[i] >> p[i]; auto d = simulateCollapse(n, t, x, y, w, p); for (int i = 0; i < q; ++i) cout << d[i] << '\n'; return 0; } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...