Submission #1198749

#TimeUsernameProblemLanguageResultExecution timeMemory
1198749alenhsiaoBridges (APIO19_bridges)C++20
0 / 100
87 ms10396 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 5e4 + 5; const int MAXQ = 1e5 + 5; struct Edge { int u, v, w, id; }; struct Query { int type; // 1=update, 2=query int t, a, b, idx; // for query: a=s, b=w }; int parent[MAXN], sz[MAXN]; int bridge_weight[MAXQ], final_weight[MAXQ]; vector<Edge> edges; vector<Query> queries; int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); } void unite(int x, int y) { x = find(x); y = find(y); if (x != y) { if (sz[x] < sz[y]) swap(x, y); parent[y] = x; sz[x] += sz[y]; } } int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; edges.resize(m); for (int i = 0; i < m; ++i) { int u, v, d; cin >> u >> v >> d; edges[i] = {u, v, d, i}; bridge_weight[i] = d; final_weight[i] = d; } int q; cin >> q; vector<pair<int, int>> mod(m, {-1, -1}); // 最後限重紀錄 vector<pair<int, pair<int, int>>> off; // {weight, {type, idx}}: type=0=edge, type=1=query vector<int> ans; for (int i = 0; i < q; ++i) { int t; cin >> t; if (t == 1) { int id, new_w; cin >> id >> new_w; --id; final_weight[id] = new_w; } else { int s, w; cin >> s >> w; queries.push_back({2, i, s, w, (int)ans.size()}); ans.push_back(0); } } // 將 edge 和 query 合併一起排序(權重大到小) vector<pair<int, int>> event; for (int i = 0; i < m; ++i) event.push_back({final_weight[i], ~i}); // edge id as ~i for (int i = 0; i < (int)queries.size(); ++i) event.push_back({queries[i].b, i}); // query index sort(event.rbegin(), event.rend()); iota(parent, parent + n + 1, 0); fill(sz, sz + n + 1, 1); vector<bool> used(m, false); for (auto [w, id] : event) { if (id < 0) { int eid = ~id; if (used[eid]) continue; unite(edges[eid].u, edges[eid].v); used[eid] = true; } else { int root = find(queries[id].a); ans[queries[id].idx] = sz[root]; } } for (int x : ans) cout << x << '\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...