Submission #967013

#TimeUsernameProblemLanguageResultExecution timeMemory
967013kilkuwuBridges (APIO19_bridges)C++17
0 / 100
3044 ms10476 KiB
#include <bits/stdc++.h> #define nl '\n' #ifdef LOCAL #include "template/debug.hpp" #else #define dbg(...) ; #define timer(...) ; #endif struct DSU { std::vector<int> e; std::vector<std::array<int, 4>> trace; DSU(int n) : e(n, -1) {} int find(int u) { return e[u] < 0 ? u : find(e[u]); } bool merge(int u, int v) { trace.push_back({-1, -1, -1, -1}); u = find(u), v = find(v); if (u == v) return false; if (e[u] > e[v]) std::swap(u, v); trace.back() = {u, e[u], v, e[v]}; e[u] += e[v]; e[v] = u; return true; } void rollback() { auto [u, eu, v, ev] = trace.back(); trace.pop_back(); if (u != -1) { e[u] = eu; e[v] = ev; } } void rollback(int size) { while ((int) trace.size() > size) { rollback(); } } int history_size() const { return trace.size(); } bool same(int u, int v) { return find(u) == find(v); } int size(int u) { return -e[find(u)]; } }; struct Edge { int u, v, d, i; bool operator<(const Edge& rhs) const { return d < rhs.d; } }; signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; std::vector<std::array<int, 3>> edges(m); for (int i = 0; i < m; i++) { int u, v, d; std::cin >> u >> v >> d; --u, --v; edges[i] = {d, u, v}; } int q; std::cin >> q; std::vector<int> ans(q, -1); const int B = 100; std::vector<int> is_changed(m, -1); std::vector<int> become(m, -1); std::vector<std::array<int, 3>> unchanged; std::vector<int> changed; unchanged.reserve(m); changed.reserve(m); for (int lb = 0; lb < q; lb += B) { int rb = std::min(lb + B, q); std::vector<std::array<int, 3>> ask; std::vector<std::array<int, 3>> upd; for (int i = lb; i < rb; i++) { int t, a, b; std::cin >> t >> a >> b; --a; if (t == 1) { is_changed[a] = lb; upd.push_back({b, a, i}); } else { ask.push_back({b, a, i}); } } unchanged.clear(); for (int i = 0; i < m; i++) { if (is_changed[i] < lb) { unchanged.emplace_back(edges[i]); } else { changed.emplace_back(i); } } std::sort(unchanged.rbegin(), unchanged.rend()); DSU dsu(n); int j = 0; std::sort(ask.rbegin(), ask.rend()); dbg(ask); dbg(changed); for (auto [w, s, id] : ask) { while (j < (int) unchanged.size() && unchanged[j][0] >= w) { dsu.merge(unchanged[j][1], unchanged[j][2]); j++; } dbg(w, s, id, j); int sz = dsu.history_size(); for (auto [r, b, uid] : upd) { if (uid <= id) { become[b] = r; } } for (int i : changed) { auto [d, u, v] = edges[i]; if (become[i] != -1) d = become[i]; if (d >= w) { dsu.merge(u, v); } } for (auto [r, b, uid] : upd) { if (uid <= id) { become[b] = -1; } } ans[id] = dsu.size(s); dsu.rollback(sz); } } for (int i = 0; i < q; i++) { if (ans[i] != -1) std::cout << ans[i] << nl; } }
#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...