제출 #336359

#제출 시각아이디문제언어결과실행 시간메모리
33635912tqian다리 (APIO19_bridges)C++17
0 / 100
2879 ms10844 KiB
#include <bits/stdc++.h> struct DSU { std::vector<int> e; void init(int n) { e = std::vector<int>(n, -1); } int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } bool same_set(int a, int b) { return get(a) == get(b); } int size(int x) { return -e[get(x)]; } bool unite(int x, int y) { x = get(x), y = get(y); if (x == y) return false; if (e[x] > e[y]) std::swap(x, y); e[x] += e[y]; e[y] = x; return true; } }; inline char gc() { // like getchar() static char buf[1 << 16]; static size_t bc, be; if (bc >= be) { buf[0] = 0, bc = 0; be = fread(buf, 1, sizeof(buf), stdin); } return buf[bc++]; // returns 0 on EOF } int read_int() { int a, c; while ((a = gc()) < 40); if (a == '-') return -read_int(); while ((c = gc()) >= 48) a = a * 10 + c - 480; return a - 48; } int main() { const int B = 800; using namespace std; int n = read_int(); int m = read_int(); vector<vector<int>> adj(n); vector<array<int, 3>> ed; set<array<int, 2>> use; for (int i = 0; i < m; i++) { int u = read_int(); int v = read_int(); int w = read_int(); u--, v--; use.insert({w, i}); ed.push_back({u, v, w}); } vector<array<int, 3>> modify; vector<array<int, 3>> queries; vector<array<int, 2>> ans; vector<int> vis(n); vector<int> mod(m); vector<int> change(m, -1); vector<int> rem; vector<int> todo; DSU D; int q = read_int(); for (int i = 0; i < q; i++) { int x = read_int(); int y = read_int(); int z = read_int(); y--; if (x == 1) modify.push_back({y, z, i}); else queries.push_back({y, z, i}); if (i == q - 1 || int(modify.size()) + int(queries.size()) == B) { sort(queries.begin(), queries.end(), [](array<int, 3>& a, array<int, 3>& b) { return a[1] > b[1]; }); D.init(n); for (auto& mm : modify) mod[mm[0]] = 1; auto it = use.end(); for (auto& qq : queries) { int weight = qq[1]; int ti = qq[2]; if (it == use.begin()) break; auto ii = (*prev(it))[1]; while (ed[ii][2] >= weight) { it = prev(it); if (!mod[ii]) D.unite(ed[ii][0], ed[ii][1]); if (it == use.begin()) break; ii = (*prev(it))[1]; } for (auto& mm : modify) { todo.push_back(mm[0]); if (mm[2] < ti) change[mm[0]] = mm[1]; } for (auto& t : todo) { if (change[t] == -1) { if (ed[t][2] >= weight) { int u = D.get(ed[t][0]); int v = D.get(ed[t][1]); adj[u].push_back(v); adj[v].push_back(u); } } else { if (change[t] >= weight) { int u = D.get(ed[t][0]); int v = D.get(ed[t][1]); adj[u].push_back(v); adj[v].push_back(u); } } } int res = 0; function<void(int)> dfs = [&](int src) { vis[src] = 1; res += D.size(src); rem.push_back(src); for (int nxt : adj[src]) { if (vis[nxt]) continue; dfs(nxt); } }; dfs(D.get(qq[0])); ans.push_back({ti, res}); for (auto& r : rem) vis[r] = 0; for (auto& t : todo) { change[t] = -1; int u = D.get(ed[t][0]); int v = D.get(ed[t][1]); adj[u].clear(); adj[v].clear(); } rem.clear(); todo.clear(); } for (auto& mm : modify) { mod[mm[0]] = 0; use.erase({ed[mm[0]][2], mm[0]}); ed[mm[0]][2] = mm[1]; use.insert({ed[mm[0]][2], mm[0]}); } queries.clear(); modify.clear(); } } sort(ans.begin(), ans.end()); for (auto& a : ans) cout << a[1] << '\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...