#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |