| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1177751 | sasde | Bridges (APIO19_bridges) | C++17 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define task "strdel"
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back
#define emb emplace_back
#define emf emplace_front
#define em emplace
using namespace std;
const int N = 5e4 + 5, mod = 1e9 + 7;
struct pt { int u, v, w; };
stack<pair<int, int>> zz;
int r[N], n, m, ans[N];
vector<pt> edges;
vector<pt> queries;
bool k[N];
unordered_map<int, int> k1;
int acs(int u) {
while (r[u] >= 0) u = r[u];
return u;
}
void join(int u, int v, int i) {
u = acs(u);
v = acs(v);
if (u == v) return;
if (r[u] > r[v]) swap(u, v);
if (i == 1) zz.emplace(v, r[v]);
r[u] += r[v];
r[v] = u;
}
void rollback() {
while (!zz.empty()) {
auto [v, val] = zz.top();
zz.pop();
r[r[v]] -= val;
r[v] = val;
}
}
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n >> m;
edges.resize(m + 1);
for (int i = 1; i <= m; ++i)
cin >> edges[i].u >> edges[i].v >> edges[i].w;
int q;
cin >> q;
queries.resize(q + 1);
for (int i = 1; i <= q; ++i)
cin >> queries[i].t >> queries[i].u >> queries[i].w;
int sq = 450;
for (int st = 1; st <= q; st += sq) {
int test = min(q, st + sq - 1);
vector<int> jo, nojo, res;
for (int i = st; i <= test; ++i) {
if (queries[i].t == 1) k[queries[i].u] = true;
else res.push_back(i);
}
for (int i = 1; i <= m; ++i) {
if (!k[i]) nojo.push_back(i);
else jo.push_back(i);
}
sort(res.begin(), res.end(), [&](int x, int y) {
return queries[x].w > queries[y].w;
});
sort(nojo.begin(), nojo.end(), [&](int x, int y) {
return edges[x].w > edges[y].w;
});
memset(r, -1, sizeof(r));
int j = 0;
for (int x : res) {
while (j < nojo.size() && edges[nojo[j]].w >= queries[x].w) {
join(edges[nojo[j]].u, edges[nojo[j]].v, 0);
++j;
}
k1.clear();
for (int z = st; z < x; ++z)
if (queries[z].t == 1)
k1[queries[z].u] = z;
for (int y : jo) {
if (k1.count(y)) {
if (queries[k1[y]].w >= queries[x].w)
join(edges[y].u, edges[y].v, 1);
} else {
if (edges[y].w >= queries[x].w)
join(edges[y].u, edges[y].v, 1);
}
}
ans[x] = -r[acs(queries[x].u)];
rollback();
}
for (int i = st; i <= test; ++i)
if (queries[i].t == 1) {
k[queries[i].u] = false;
edges[queries[i].u].w = queries[i].w;
}
}
for (int i = 1; i <= q; ++i)
if (queries[i].t == 2)
cout << ans[i] << '\n';
}
int main() {
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
solve();
return 0;
}