This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
#define N 50001
#define M 100001
int lnk[N], sz[N];
void build(int n){
fill(sz, sz+n+1, 1);
iota(lnk, lnk+n+1, 0);
}
int root(int x){
return lnk[x] == x ? x : (lnk[x] = root(lnk[x]));
}
void unite(int x, int y){
x = root(x), y = root(y);
if (x == y) return;
if (sz[x] < sz[y]) swap(x, y);
sz[x] += sz[y];
lnk[y] = x;
}
struct Edge {
int a, b, w, i;
bool operator < (const Edge &o) const { return w > o.w; }
};
Edge edges[M], sorted[M], queries[M];
vector<int> adj[N];
bool vis[N];
int ans[M];
int32_t main(){
// input
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m; cin >> n >> m;
for (int i = 1; i <= m; i++){
cin >> edges[i].a >> edges[i].b >> edges[i].w;
edges[i].i = i;
}
int q; cin >> q;
for (int i = 1; i <= q; i++){
cin >> queries[i].a >> queries[i].b >> queries[i].w;
queries[i].i = i;
}
int bsz = ceil(sqrt(q));
for (int s = 1; s <= q; s += bsz){
build(n);
vector<Edge> qu;
map<int, int> changed;
for (int i = s; i < min(q+1, s+bsz); i++){
if (queries[i].a == 1)
changed[queries[i].b] = edges[queries[i].b].w;
else
qu.push_back(queries[i]);
}
sort(qu.begin(), qu.end());
for (int i = 1; i <= m; i++)
sorted[i] = edges[i];
sort(sorted+1, sorted+m+1);
int j = 1;
for (auto [_, s, w, idx] : qu){
for (; j <= m && sorted[j].w >= w; j++)
if (!changed.count(sorted[j].i))
unite(sorted[j].a, sorted[j].b);
map<int, int> curr(changed);
for (int i = s; i < idx; i++)
if (queries[i].a == 1)
curr[queries[i].b] = queries[i].w;
for (auto [ei, ew] : curr){
if (ew >= w && root(edges[ei].a) != root(edges[ei].b)){
adj[root(edges[ei].a)].push_back(root(edges[ei].b));
adj[root(edges[ei].b)].push_back(root(edges[ei].a));
}
}
fill(vis, vis+n+1, false);
queue<int> q;
q.push(root(s));
vis[root(s)] = true;
while (!q.empty()){
int u = q.front();
q.pop();
ans[idx] += sz[u];
for (int v : adj[u]){
if (!vis[v]){
vis[v] = true;
q.push(v);
}
}
}
for (auto [ei, ew] : curr){
adj[root(edges[ei].a)].clear();
adj[root(edges[ei].b)].clear();
}
}
for (int i = s; i < min(q+1, s+bsz); i++)
if (queries[i].a == 1)
changed[queries[i].b] = queries[i].w;
for (auto [i, w] : changed)
edges[i].w = w;
}
for (int i = 1; i <= q; i++)
if (ans[i])
cout << ans[i] << '\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... |