| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1063103 | manhlinh1501 | 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.
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using pii = pair<int, int>;
const int MAXN = 1e5 + 5;
const int oo32 = 1e9 + 5;
const int BLOCK_SIZE = 1000;
#define prev ___prev
struct event {
int type, x, y, p;
event(int type = 0, int x = 0, int y = 0, int p = 0): type(type), x(x), y(y), p(p) {}
};
struct edge {
int u, v, w;
edge(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}
};
int N, M, Q;
edge e[MAXN];
event query[MAXN];
int ans[MAXN];
struct DSU {
int lab[MAXN];
vector<tuple<int, int, int, int>> rb;
void init(int N) {
for(int i = 1; i <= N; i++)
lab[i] = -1;
}
int root(int u) {
if (lab[u] < 0)
return u;
return root(lab[u]);
}
bool join(int u, int v) {
u = root(u);
v = root(v);
if (u == v)
return false;
if (lab[u] > lab[v])
swap(u, v);
lab[u] += lab[v];
lab[v] = u;
return true;
}
int size(int u) {
return -lab[root(u)];
}
bool join_with_rollback(int u, int v) {
u = root(u);
v = root(v);
if (u == v)
return false;
if (lab[u] > lab[v])
swap(u, v);
rb.emplace_back(u, lab[u], v, lab[v]);
lab[u] += lab[v];
lab[v] = u;
return true;
}
void rollback() {
auto [u, _u, v, _v] = rb.back();
rb.pop_back();
lab[u] = _u;
lab[v] = _v;
}
void rollback_all() {
while(!rb.empty()) rollback();
}
} dsu;
bool is_change[MAXN];
int idx[MAXN];
vector<edge> prev[MAXN];
edge ne[MAXN];
void process(int l, int r) {
dsu.init(N);
vector<int> changed_edge;
for(int i = 1; i <= M; i++) {
ne[i] = e[i];
is_change[i] = false;
idx[i] = i;
}
sort(idx + 1, idx + M + 1, [&](const int a, const int b) {
return e[a].w > e[b].w;
});
for(int i = l; i <= r; i++) {
auto [type, x, y, p] = query[i];
if(type == 1)
is_change[x] = true;
}
for(int i = 1; i <= M; i++) {
if(is_change[i])
changed_edge.emplace_back(i);
}
for(int i = l; i <= r; i++) {
auto [type, x, y, p] = query[i];
if(type == 1)
e[x].w = y;
else {
for(int z : changed_edge)
prev[i].emplace_back(e[z]);
}
}
sort(query + l, query + r + 1, [&](const event a, const event b) {
return a.y > b.y;
});
int j = 1;
for(int i = l; i <= r; i++) {
auto [type, x, y, p] = query[i];
if(type == 1)
continue;
while(j <= M and ne[idx[j]].w >= y) {
if(is_change[idx[j]] == false) {
dsu.join(ne[idx[j]].u, ne[idx[j]].v);
}
j++;
}
for(auto [u, v, w] : prev[p]) {
if(w >= y) dsu.join_with_rollback(u, v);
}
ans[p] = dsu.size(x);
dsu.rollback_all();
}
}
signed main() {
#define TASK "code"
if (fopen(TASK ".inp", "r")) {
freopen(TASK ".inp", "r", stdin);
freopen(TASK ".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N >> M;
for(int i = 1; i <= M; i++) {
auto &[u, v, w] = e[i];
cin >> u >> v >> w;
}
cin >> Q;
for(int i = 1; i <= Q; i++) {
auto &[type, x, y, p] = query[i];
cin >> type >> x >> y;
p = i;
}
for(int i = 1; i <= Q; i++) ans[i] = -1;
for(int i = 1; i <= Q; i += BLOCK_SIZE) {
process(i, min(Q, i + BLOCK_SIZE - 1));
}
for(int i = 1; i <= Q; i++) {
if(ans[i] == -1)
continue;
cout << ans[i] << "\n";
}
return (0 ^ 0);
}