Submission #1218284

#TimeUsernameProblemLanguageResultExecution timeMemory
1218284polarity다리 (APIO19_bridges)C++20
59 / 100
3090 ms7440 KiB
/** * Solution by Charles Ran (polarity.sh) * Date: 2025-06-14 * Contest: APIO 2019 * Problem: bridges **/ #include <bits/stdc++.h> #pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") using namespace std; using ull = unsigned long long; using ll = long long; using vi = vector<int>; using vl = vector<ll>; using pii = pair<int, int>; #define pb push_back #define rep(i, a, b) for(int i = (a); i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() const int MAX_N = 1e5 + 1; const ll MOD = 1e9 + 7; /** * DS: Disjoint Set Union * PURPOSE: Dynamically updates connectedness of graph by adding edges * TIME: amortized O(a(N)) to query */ class DSU { private: vector<int> parents; vector<int> sizes; public: DSU(int size) : parents(size), sizes(size, 1){ for (int i = 0; i < size; i++){ parents[i] = i; } } int find(int x){ return (parents[x] == x ? x : parents[x] = find(parents[x])); } int getSize(int x){ return sizes[find(x)]; } bool unite(int a, int b){ int parentA = find(a); int parentB = find(b); if (parentA == parentB){ return false; } if (sizes[parentA] > sizes[parentB]){ swap(parentA, parentB); } sizes[parentB] += sizes[parentA]; parents[parentA] = parentB; return true; } bool connected(int a, int b){ return find(a) == find(b); } }; array<int, 3> bridges[MAX_N]; array<int, 3> qs[MAX_N]; bool changed[MAX_N]; bool checked[50001]; int ans[MAX_N]; void solve(){ int n, m; cin >> n >> m; rep(i, 0, m){ int a, b, d; cin >> a >> b >> d; --a; --b; bridges[i] = {d, a, b}; } int q; cin >> q; int rt = sqrt(q); rep(i, 0, q){ int t, a, b; cin >> t >> a >> b; qs[i] = {t, a, b}; } vector<vi> adj(n); DSU dsu(n); vector<bool> visited(n, false); rep(i, 0, q/rt + 1){ vector<array<int, 3>> changes; vector<array<int, 4>> queries; int ac = 0; rep(j, 0, rt){ int idx = i * rt + j; if (idx >= q) break; auto &[t, a, b] = qs[idx]; if (t == 1){ changes.pb({a - 1, b, idx}); changed[a - 1] = true; ac++; } else { queries.pb({b, a - 1, idx, ac}); } } int nn = changes.size(); sort(queries.rbegin(), queries.rend()); vector<array<int, 3>> sb; reverse(all(changes)); rep(j, 0, m){ if (!changed[j]){ sb.pb(bridges[j]); } else { changes.pb({j, bridges[j][0], -1}); } } sort(sb.rbegin(), sb.rend()); int idx = 0; DSU dsu(n); rep(k, 0, queries.size()){ auto &[w, a, j, qac] = queries[k]; while (idx < sb.size() && sb[idx][0] >= w){ dsu.unite(sb[idx][1], sb[idx][2]); idx++; } vi checks; vi edges; rep (kk, nn - qac, changes.size()){ array<int, 3> &change = changes[kk]; int b = change[0]; if (checked[b]) continue; checked[b] = true; checks.pb(b); if (change[1] >= w){ int fa = dsu.find(bridges[b][1]); int fb = dsu.find(bridges[b][2]); if (fa == fb) continue; edges.pb(fa); edges.pb(fb); adj[fa].pb(fb); adj[fb].pb(fa); } } for (int b : checks){ checked[b] = false; } vi vis; function<int(int)> dfs; dfs = [&](int x){ if (visited[x]){ return 0; } visited[x] = true; vis.pb(x); int ans = 0; for (int node : adj[x]){ ans += dfs(node); } return ans + dsu.getSize(x); }; ans[j] = dfs(dsu.find(a)); for (int e : edges){ adj[e].clear(); } for (int v : vis){ visited[v] = false; } } reverse(all(changes)); for (array<int, 3> change : changes){ bridges[change[0]][0] = change[1]; changed[change[0]] = false; } } rep(i, 0, q){ if (ans[i]){ cout << ans[i] << endl; } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); 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...
#Verdict Execution timeMemoryGrader output
Fetching results...