제출 #649155

#제출 시각아이디문제언어결과실행 시간메모리
649155LeonaRaging다리 (APIO19_bridges)C++14
27 / 100
1717 ms524288 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #define pb push_back #define db(val) "[" #val " = " << (val) << "] " const ll mod = 1e9 + 7; const int maxn = 5e4 + 3; const int INF = 1e9; const int block = 1e9; struct Edge { int u, v, w; Edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w) {} } edges[2 * maxn]; struct Query { int t, x, y; Query(int t = 0, int x = 0, int y = 0): t(t), x(x), y(y) {} } quy[2 * maxn]; int n, m, q, res[2 * maxn]; stack<int> st; bool bad[2 * maxn]; vector<int> upd[2 * maxn], change, unchange, ask; struct DisjointSet { int par[maxn], Rank[maxn]; int find(int x) { while (x != par[x]) x = par[x]; return x; } bool join(int u, int v) { u = find(u); v = find(v); if (u == v) return 0; if (Rank[u] < Rank[v]) swap(u, v); st.push(v); Rank[u] += Rank[v]; par[v] = u; return 1; } void rollback(int x) { while ((int)st.size() > x) { int u = st.top(); st.pop(); Rank[par[u]] -= Rank[u]; par[u] = u; } } } Dsu; void reset() { for (int i = 1; i <= n; i++) { Dsu.par[i] = i; Dsu.Rank[i] = 1; } for (int i = 1; i <= m; i++) bad[i] = false; vector<int>().swap(change); vector<int>().swap(unchange); vector<int>().swap(ask); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen(".INP", "r", stdin); //freopen(".OUT", "w", stdout); cin >> n >> m; for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; edges[i] = {u, v, w}; } cin >> q; for (int i = 1; i <= q; i++) { int t, x, y; cin >> t >> x >> y; quy[i] = {t, x, y}; } for (int l = 1; l <= q; l += block) { int r = min(l + block - 1, q); reset(); for (int i = l; i <= r; i++) if (quy[i].t == 1) bad[quy[i].x] = true; for (int i = 1; i <= m; i++) if (!bad[i]) unchange.pb(i); else change.pb(i); for (int i = l; i <= r; i++) { if (quy[i].t == 1) edges[quy[i].x].w = quy[i].y; else { ask.pb(i); vector<int>().swap(upd[i]); for (auto k : change) if (edges[k].w >= quy[i].y) upd[i].pb(k); } } sort(unchange.begin(), unchange.end(),[&] (int i, int j) { return edges[i].w > edges[j].w; }); sort(ask.begin(), ask.end(),[&](int i, int j) { return quy[i].y > quy[j].y; }); int pos = 0; for (int i : ask) { while (pos < (int)unchange.size() && quy[i].y <= edges[unchange[pos]].w) { Dsu.join(edges[unchange[pos]].u, edges[unchange[pos]].v); pos++; } int sz = st.size(); for (int k : upd[i]) Dsu.join(edges[k].u, edges[k].v); quy[i].x = Dsu.find(quy[i].x); res[i] = Dsu.Rank[quy[i].x]; Dsu.rollback(sz); } } for (int i = 1; i <= q; i++) if (res[i]) cout << res[i] << '\n'; }
#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...