#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair
const int mxn = 1e5 + 10;
const int BLOCK_sz = 550;
int n, m, q, weight[mxn];
vector<pii> edges(mxn);
vector<pii> query(mxn);
bool changed[mxn];
int type[mxn];
int ans[mxn];
namespace DSU {
int par[mxn];
stack<pair<pii, pii>> hist;
int parent(int u) { return par[u] < 0 ? u : parent(par[u]); }
void unite(int u, int v) {
u = parent(u);
v = parent(v);
if(u == v) return;
if(par[u] > par[v]) swap(u, v);
hist.push(MP(MP(u, par[u]), MP(v, par[v])));
par[u] += par[v];
par[v] = u;
}
void roll() {
if(hist.empty()) return;
int u, v, pu, pv;
tie(u, pu) = hist.top().ff;
tie(v, pv) = hist.top().ss;
par[u] = pu;
par[v] = pv;
hist.pop();
}
void roll_back(int sz) {
while(hist.size() > sz) {
int u, pu, v, pv;
tie(u, pu) = hist.top().ff;
tie(v, pv) = hist.top().ss;
par[u] = pu;
par[v] = pv;
hist.pop();
}
}
void clear(int n) {
memset(par, -1, sizeof(int) * (n + 5));
while(hist.size()) hist.pop();
}
};
int main() {
cin >> n >> m;
for(int i = 1; i <= m; i++) {
cin >> edges[i].ff >> edges[i].ss >> weight[i];
}
cin >> q;
for(int i = 0; i < q; i++) {
cin >> type[i] >> query[i].ff >> query[i].ss;
}
for(int L = 0; L < q; L += BLOCK_sz) {
int R = min(L + BLOCK_sz, q);
for(int i = 1; i <= m; i++)
changed[i] = 0;
vector<int> ask;
for(int i = L; i < R; i++) {
int x = query[i].ff;
int w = query[i].ss;
if(type[i] == 1) {
changed[x] = 1;
}
else {
ask.push_back(i);
}
}
vector<int> CH, UC;
for(int i = 1; i <= m; i++)
if(changed[i])
CH.push_back(i);
else
UC.push_back(i);
sort(ask.begin(), ask.end(), [&](int i, int j) { return query[i].ss > query[j].ss; });
sort(UC.begin(), UC.end(), [&](int i, int j) { return weight[i] > weight[j]; });
DSU::clear(n);
int ptr = 0;
for(int i : ask) {
const int u = query[i].ff;
const int w = query[i].ss;
while(ptr < UC.size()) {
int e = UC[ptr];
if(weight[e] < w) break;
int x = edges[e].ff;
int y = edges[e].ss;
DSU::unite(x, y);
ptr++;
}
const int snap = DSU::hist.size();
for(int j = L; j < i; j++) {
if(type[j] == 2) continue;
int E = query[j].ff;
int W = query[j].ss;
if(W >= w) {
int x = edges[E].ff;
int y = edges[E].ss;
DSU::unite(x, y);
}
}
for(int j = i + 1; j < R; j++) {
if(type[j] == 2) continue;
int E = query[j].ff;
int W = weight[E];
if(W >= w) {
int x = edges[E].ff;
int y = edges[E].ss;
DSU::unite(x, y);
}
}
int p = DSU::parent(u);
ans[i] = -DSU::par[p];
DSU::roll_back(snap);
}
for(int i = L; i < R; i++) {
if(type[i] == 2) continue;
int e = query[i].ff;
int w = query[i].ss;
weight[e] = w;
}
}
for(int i = 0; i < q; i++) {
if(type[i] == 2) {
cout << ans[i] << endl;
}
}
}
# | 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... |