제출 #684494

#제출 시각아이디문제언어결과실행 시간메모리
684494noedit다리 (APIO19_bridges)C++17
100 / 100
2286 ms7580 KiB
#include <bits/stdc++.h> //#include <quadmath.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //#define sz(x) (int)x.size() //#define sqr(x) x*x #pragma GCC optimize("-O3") #pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("fast-math") using namespace std; //using namespace __gnu_pbds; // //#define int long long ////#define ld long double //template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long ll; const int MAXN = 5e4 + 5; const int B = 1400; const int MAXQ = 1e5 + 5; int sz[MAXN], p[MAXN]; array<int, 4> rb[MAXQ]; int rb_pt = 0; int edges[B]; int active[MAXQ]; int edges_pt = 0; void init(int n) { rb_pt = 0; fill(sz, sz + n, 1); iota(p, p + n, 0); } int get_par(int a) { if (p[a] == a) return a; return get_par(p[a]); } void mrg(int a, int b) { a = get_par(a); b = get_par(b); if (a != b) { if (sz[a] < sz[b]) swap(a, b); rb[rb_pt++] = {b, a, p[b], sz[a]}; sz[a] += sz[b]; p[b] = a; } } void rollback(int x) { while (rb_pt > x) { auto&[b, a, pb, sza] = rb[rb_pt - 1]; rb_pt--; p[b] = pb; sz[a] = sza; } } void solve() { int n, m; cin >> n >> m; vector<array<int, 3> > es(m); for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; u--; v--; es[i] = {w, u, v}; } int q; cin >> q; vector<array<int, 3> > qs(q); for (int i = 0; i < q; i++) { int t, u, w; cin >> t >> u >> w; u--; qs[i] = {t, u, w}; } vector<int> ans(q, -1); int active_flag = 0; for (int i = 0; i < q; i += B) { //vector<bool> active(m); active_flag++; //vector<int> edges; edges_pt = 0; auto ess = es; //edges.reserve(B); vector<array<int, 4> > act; act.reserve(B + m); for (int j = i; j < min(q, i + B); j++) { auto& [t, u, w] = qs[j]; if (t == 1) { active[u] = active_flag; ess[u][0] = w; edges[edges_pt++] = j; } else { act.push_back({w, 0, u, j}); } } sort(edges, edges + edges_pt, [&](int a, int b) { return qs[a][1] < qs[b][1] || (qs[a][1] == qs[b][1] && a < b); }); for (int j = 0; j < m; j++) { auto& [w, u, v] = es[j]; if (active[j] != active_flag) { act.push_back({w, 1, u, v}); } } sort(act.rbegin(), act.rend()); init(n); for (auto& [w, t, u, v] : act) { if (t == 0) { int kek = rb_pt; for (int k = 0; k < (int)edges_pt;) { int bebra = k; int wei = -1; while (bebra < (int)edges_pt && qs[edges[bebra]][1] == qs[edges[k]][1]) { if (edges[bebra] < v) { wei = qs[edges[bebra]][2]; } ++bebra; } int numb = qs[edges[k]][1]; if (wei == -1) { wei = es[numb][0]; } if (w <= wei) { mrg(es[numb][1], es[numb][2]); } k = bebra; } ans[v] = sz[get_par(u)]; rollback(kek); } else { mrg(u, v); } } es = ess; } for (auto& i : ans) { if (i != -1) cout << i << '\n'; } } // signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; t = 1; while (t--) { solve(); } cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl; return 0; } // // ///* //4 4 //1 2 1 3 //1 1 //1 2 //1 3 //1 4 //*/
#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...