Submission #938016

#TimeUsernameProblemLanguageResultExecution timeMemory
938016mat_jurBridges (APIO19_bridges)C++17
0 / 100
3037 ms38364 KiB
#include <bits/stdc++.h> using namespace std; #ifdef DEBUG auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;} auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";} #define debug(X) cerr << "["#X"]: " << X << '\n'; #else #define cerr if(0)cout #define debug(X) ; #endif #define ll long long #define all(v) (v).begin(), (v).end() #define ssize(x) int(x.size()) #define fi first #define se second #define mp make_pair #define eb emplace_back struct dynamicUF { vector<int> e; dynamicUF(int n): e(n, -1) {} stack<array<int, 3>> s; int get(int a) {return e[a] < 0 ? a : get(e[a]);} int unionn(int a, int b) { a = get(a); b = get(b); if(a == b) return 0; if(e[a] > e[b]) swap(a, b); s.push({a, b, e[a]}); e[b] += e[a]; e[a] = b; return 1; } void roll_back(int m = 1) { while (m--) { auto [a, b, sz] = s.top(); s.pop(); assert(sz < 0); e[b] -= sz; e[a] = sz; } } }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> w(m), u(m), v(m); for(int i = 0; i < m; ++i) { cin >> u[i] >> v[i] >> w[i]; u[i]--; v[i]--; } int q; cin >> q; vector<int> ans(q, -1); const int B = 320; vector<array<int, 4>> ev; vector<bool> changed(m); vector<array<int, 3>> upd; auto clean = [&] { debug(upd); debug(changed); debug(ev); dynamicUF sp(n); for(int i = 0; i < m; ++i) { if(!changed[i]) {ev.eb((array<int, 4>){w[i], u[i], v[i], 0}); changed[i] = false;} } sort(all(ev), [&](array<int, 4> x, array<int, 4> y) { if (x[0] != y[0]) return x[0] > y[0]; return x[3] < y[3]; }); debug(ev); for(auto [d, a, b, c] : ev) { if(c == 0) { sp.unionn(a, b); } else { debug(sp.e); map<int, int> M; for(auto [idx, r, t] : upd) { if(t <= b) M[idx] = r; else M[idx] = w[idx]; } int cnt = 0; for(auto [idx, r] : M) { if(r >= d) cnt += sp.unionn(u[idx], v[idx]); } debug(cnt); debug(sp.e); ans[b] = -sp.e[sp.get(a)]; sp.roll_back(cnt); } } for(auto [idx, r, t] : upd) { w[idx] = r; } upd.clear(); }; for(int t = 0; t < q; ++t) { int c; cin >> c; if(c == 1) { int b, r; cin >> b >> r; b--; changed[b] = true; upd.eb((array<int, 3>){b, r, t}); } else { int d, s; cin >> s >> d; s--; ev.eb((array<int, 4>){d, s, t, 1}); } if(t%B == B-1) { clean(); } } clean(); debug(ans); for(int i = 0; i < q; i++) if(ans[i] > -1) cout << ans[i] << '\n'; 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...