Submission #1208789

#TimeUsernameProblemLanguageResultExecution timeMemory
1208789k1r1t0Bridges (APIO19_bridges)C++20
100 / 100
2723 ms15080 KiB
#include <bits/stdc++.h> using namespace std; const int S = 1000; const int N = 110000; int n, m, q, p[N], s[N], res[N]; vector<array<int, 3>> edge; set<array<int, 4>> sorted; bool bad[N], used[N], vrt[N]; vector<int> gr[N]; int dfs(int v) { if (vrt[v]) return 0; vrt[v] = true; int ans = s[v]; for (int u : gr[v]) ans += dfs(u); return ans; } void init() { for (int i = 1; i <= n; i++) { p[i] = i; s[i] = 1; } } int getp(int x) { return p[x] == x ? x : p[x] = getp(p[x]); } void unite(int a, int b) { a = getp(a); b = getp(b); if (a == b) return; if (s[a] < s[b]) swap(a, b); s[a] += s[b]; p[b] = a; } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v, d; cin >> u >> v >> d; edge.push_back({u, v, d}); sorted.insert({d, u, v, i - 1}); } cin >> q; vector<array<int, 3>> qq; for (int i = 1; i <= q; i++) { int a, b, c; cin >> a >> b >> c; if (a == 1) b--; qq.push_back({a, b, c}); if (i == q || (int) qq.size() == S) { for (int i = 0; i < m; i++) bad[i] = false; for (auto [a, b, c] : qq) if (a == 1) bad[b] = true; vector<array<int, 3>> good; vector<int> tbad; for (auto [a, b, c, d] : sorted) if (!bad[d]) good.push_back({b, c, a}); else tbad.push_back(d); reverse(begin(good), end(good)); vector<array<int, 3>> gg; for (int i = 0; i < (int) qq.size(); i++) if (qq[i][0] == 2) gg.push_back({qq[i][2], qq[i][1], i}); sort(begin(gg), end(gg)); reverse(begin(gg), end(gg)); init(); int ptr = 0; for (auto [a, b, c] : gg) { while (ptr < (int) good.size() && good[ptr][2] >= a) { unite(good[ptr][0], good[ptr][1]); ptr++; } for (int i = c; i >= 0; i--) { if (qq[i][0] == 2 || used[qq[i][1]]) continue; used[qq[i][1]] = true; if (qq[i][2] >= a) { int x = edge[qq[i][1]][0]; int y = edge[qq[i][1]][1]; x = getp(x); y = getp(y); if (x == y) continue; gr[x].push_back(y); gr[y].push_back(x); } } for (int k : tbad) if (!used[k] && edge[k][2] >= a) { used[k] = true; int x = edge[k][0]; int y = edge[k][1]; x = getp(x); y = getp(y); if (x == y) continue; gr[x].push_back(y); gr[y].push_back(x); } res[c] = dfs(getp(b)); vrt[getp(b)] = false; for (int k : tbad) { if (!used[k]) continue; used[k] = false; int x = edge[k][0]; int y = edge[k][1]; x = getp(x); y = getp(y); if (x == y) continue; gr[x].clear(); gr[y].clear(); vrt[x] = vrt[y] = false; } } for (int i = 0; i < (int) qq.size(); i++) if (qq[i][0] == 2) cout << res[i] << '\n'; for (auto [a, b, c] : qq) if (a == 1) { sorted.erase({edge[b][2], edge[b][0], edge[b][1], b}); edge[b][2] = c; sorted.insert({edge[b][2], edge[b][0], edge[b][1], b}); } qq.clear(); } } }
#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...