| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 529301 | dutinmeow | Bridges (APIO19_bridges) | C++17 | 0 ms | 0 KiB |
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;
struct RollbackUnionFind {
vector<int> par, siz;
stack<int> rev;
RollbackUnionFind() = default;
RollbackUnionFind(int n) { init(n); }
void init(int n) {
par.resize(n);
siz.resize(n);
iota(par.begin(), par.end(), 0);
fill(siz.begin(), siz.end(), 1);
}
int find(int u) {
while (u != par[u])
u = par[u];
return u;
}
bool merge(int u, int v) {
u = find(u), v = find(v);
if (u == v)
return false;
if (siz[u] > siz[v]) {
par[v] = u;
siz[u] += siz[v];
rev.push(v);
} else {
par[u] = v;
siz[v] += siz[u];
rev.push(u);
}
return true;
}
int size(int u) { return siz[find(u)]; }
void rollback() {
int u = rev.top(); rev.pop();
siz[par[u]] -= siz[u];
par[u] = u;
}
void rollback(size_t s) {
while (rev.size() > s)
rollback();
}
};
int main() {
int N, M, Q;
cin >> N >> M;
struct edge { int u, v, w; };
vector<edge> E; E.reserve(M);
for (int i = 0; i < M; i++) {
int u, v, w;
cin >> u >> v >> w;
E.emplace_back(u - 1, v - 1, w);
}
cin >> Q;
struct oper { int t, a, b; };
vector<oper> Z; Z.reserve(Q);
for (int i = 0; i < Q; i++) {
int t, a, b;
cin >> t >> a >> b;
Z.emplace_back(t, a - 1, b);
}
/*
cout << N << ' ' << M << '\n';
for (auto [u, v, w] : E)
cout << "edge " << u << ' ' << v << ' ' << w << '\n';
cout << Q << '\n';
for (auto [t, a, b] : Z)
cout << "oper " << t << ' ' << a << ' ' << b << '\n';
*/
RollbackUnionFind rdsu;
vector<int> ans(Q);
const int BLOCK_SIZE = 800;
for (int q = 0; q < Q; q += BLOCK_SIZE) {
int ql = q, qr = min(Q, q + BLOCK_SIZE);
vector<bool> B(M, false);
vector<int> C, D, Y;
vector<vector<int>> J(qr - ql);
// B = edge is changed
// C = operation indicies of changed edges
// D = unchanged edges
// Y = operation indicies of queried nodes
// J = changed indicies to be merged
for (int i = ql; i < qr; i++) {
auto [t, a, b] = Z[i];
if (t == 1) {
B[a] = true;
C.push_back(i);
} else if (t == 2) {
Y.push_back(i);
}
}
for (int i = 0; i < M; i++)
if (!B[i])
D.push_back(i);
for (int i = ql; i < qr; i++) {
auto [t, a, b] = Z[i];
if (t == 1) {
E[a].w = b;
} else if (t == 2) {
for (int c : C)
if (E[Z[c].a].w >= b)
J[i - ql].push_back(c);
}
}
sort(D.begin(), D.end(), [&E](const int i, const int j) { return E[i].w > E[j].w; });
sort(Y.begin(), Y.end(), [&Z](const int i, const int j) { return Z[i].b > Z[j].b; });
rdsu.init(N);
for (int i = 0, j = 0; i < Y.size(); i++) {
auto [t, u, w] = Z[Y[i]];
assert(t == 2);
for (; j < D.size() && E[D[j]].w >= w; j++)
rdsu.merge(E[D[j]].u, E[D[j]].v);
int s = rdsu.rev.size();
for (int c : J[Y[i] - ql])
rdsu.merge(E[Z[c].a].u, E[Z[c].a].v);
ans[Y[i]] = rdsu.size(u);
rdsu.rollback(s);
}
}
for (int i = 0; i < Q; i++)
if (Z[i].t == 2)
cout << ans[i] << '\n';
}