This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) { return l + rnd() % (r - l + 1); }
const int MAXN = 1e5 + 5;
int nBlock = 505;
int N, M, Q, ans[MAXN];
struct Edge{
int u, v, w;
} e[2 * MAXN];
struct DSU_roll_back{
vector <int> lab, rnk;
stack <int> dsu_save;
DSU_roll_back() {};
DSU_roll_back(int _n) {
lab.assign(_n + 1, 0);
iota(lab.begin(), lab.end(), 0);
rnk.assign(_n + 1, 1);
}
int get(int u) {return lab[u] == u ? u : get(lab[u]);}
bool merge(int u, int v) {
if ((u = get(u)) == (v = get(v))) return false;
if (rnk[u] < rnk[v]) swap(u, v);
rnk[u] += rnk[v];
dsu_save.push(v);
return lab[v] = u, true;
}
int data() {return dsu_save.size();}
void roll_back(int version) {
while (dsu_save.size() > version) {
int u = dsu_save.top(); dsu_save.pop();
rnk[lab[u]] -= rnk[u];
lab[u] = u;
}
}
};
bool current_change[MAXN];
signed main(void) {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> N >> M;
FOR(i, 1, M) cin >> e[i].u >> e[i].v >> e[i].w;
cin >> Q;
FOR(i, 1, Q) cin >> e[i + M].u >> e[i + M].v >> e[i + M].w;
for (int l = 1; l <= Q; l += nBlock) {
int r = min(Q, l + nBlock - 1);
vector <int> queries;
vector <int> changed;
FOR(i, l, r) {
if (e[i + M].u == 1) {
changed.emplace_back(i);
current_change[e[i + M].v] = true;
}
else {
queries.emplace_back(i + M);
}
}
FOR(i, 1, M) {
if (current_change[i] == false) {
queries.emplace_back(i);
} else current_change[i] = false;
}
sort(ALL(queries), [&] (int x, int y) {
if (e[x].w != e[y].w) return e[x].w > e[y].w;
return x < y;
});
reverse(ALL(changed));
DSU_roll_back ds(N);
for (int x : queries) {
if (x <= M) {
ds.merge(e[x].u, e[x].v);
}
else {
int ver = ds.data();
for (int y : changed) if (y <= x - M) {
int id = e[y + M].v;
if (current_change[id] == false) {
current_change[id] = true;
if (e[y + M].w >= e[x].w) {
ds.merge(e[id].u, e[id].v);
}
}
}
for (int y : changed) if (y > x - M) {
int id = e[y + M].v;
if (current_change[id] == true) continue;
if (e[id].w >= e[x].w) ds.merge(e[id].u, e[id].v);
}
ans[x - M] = ds.rnk[ds.get(e[x].v)];
ds.roll_back(ver);
for (int y : changed) if (y <= x - M) {
int id = e[y + M].v;
current_change[id] = false;
}
}
}
FOR(i, l, r) if (e[i + M].u == 1) {
int id = e[i + M].v;
e[id].w = e[i + M].w;
}
}
FOR(i, 1, Q) if (e[i + M].u == 2)
cout << ans[i] << '\n';
cerr << "Time elapsed: " << TIME << " s.\n";
return (0 ^ 0);
}
Compilation message (stderr)
bridges.cpp: In member function 'void DSU_roll_back::roll_back(int)':
bridges.cpp:45:32: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
45 | while (dsu_save.size() > version) {
| ~~~~~~~~~~~~~~~~^~~~~~~~~
# | 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... |