제출 #866084

#제출 시각아이디문제언어결과실행 시간메모리
866084qthang2k11다리 (APIO19_bridges)C++17
59 / 100
3051 ms7292 KiB
// [+] #include <bits/stdc++.h> using namespace std; const int N = 5e4 + 5, M = 1e5 + 5, Q = M, S = sqrt(Q); int n, m, q, u[M], v[M], w[M]; int par[N], num[N]; bool changed[M]; bool vs[N]; inline int find(int x) { if (par[x] != x) par[x] = find(par[x]); return par[x]; } void join(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (num[x] < num[y]) swap(x, y); num[x] += num[y]; par[y] = x; } int t[Q], x[Q], y[Q], ans[Q]; vector<int> edges[Q / S + 5], adj[N]; int dfs(int x) { vs[x] = true; int ans = num[x]; for (int y: adj[x]) if (!vs[y]) ans += dfs(y); return ans; } int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for (int i = 1; i <= m; i++) cin >> u[i] >> v[i] >> w[i]; cin >> q; for (int i = 1; i <= q; i++) cin >> t[i] >> x[i] >> y[i]; for (int L = 1; L <= q; L += S) { int R = min(q, L + S - 1); fill(num + 1, num + n + 1, 1); iota(par + 1, par + n + 1, 1); fill(changed + 1, changed + m + 1, 0); vector<int> ask, unchanged, upd; for (int i = L; i <= R; i++) { if (t[i] == 1) { changed[x[i]] = true; upd.emplace_back(i); } else ask.emplace_back(i); } for (int i = 1; i <= m; i++) if (!changed[i]) unchanged.emplace_back(i); int ucsz = unchanged.size(); for (int i = L; i <= R; i++) { if (t[i] == 1) w[x[i]] = y[i]; else { edges[i - L].clear(); for (int id: upd) if (w[x[id]] >= y[i]) edges[i - L].emplace_back(x[id]); } } sort(ask.begin(), ask.end(), [&] (int a, int b) { return y[a] > y[b]; }); sort(unchanged.begin(), unchanged.end(), [&] (int a, int b) { return w[a] > w[b]; }); int p = -1; for (int id: ask) { while (p + 1 < ucsz && w[unchanged[p + 1]] >= y[id]) ++p, join(u[unchanged[p]], v[unchanged[p]]); for (int eid: edges[id - L]) { int x = find(u[eid]), y = find(v[eid]); adj[x].emplace_back(y); adj[y].emplace_back(x); } ans[id] = dfs(find(x[id])); vs[find(x[id])] = false; for (int eid: edges[id - L]) { int x = find(u[eid]), y = find(v[eid]); adj[x].clear(); adj[y].clear(); vs[x] = vs[y] = false; } } } for (int i = 1; i <= q; i++) if (t[i] == 2) 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...