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;
#define ll long long
const int N = 100'005, B = 300;
int par[N], sz[N], par2[N], sz2[N];
int find(int u) {
if (u == par[u]) {
return u;
}
return par[u] = find(par[u]);
}
void join(int u, int v) {
u = find(u), v = find(v);
if (u == v) return;
if (sz[u] < sz[v]) swap(u, v);
par[v] = u;
sz[u] += sz[v];
}
vector<int> in;
void add(int u) {
in.push_back(u);
par2[u] = par[u];
sz2[u] = sz[u];
}
int find2(int u) {
if (par2[u] == -1) {
add(u);
}
if (par2[u] == u) {
return u;
}
return par2[u] = find2(par2[u]);
}
void join2(int u, int v) {
u = find2(u), v = find2(v);
if (u == v) return;
if (sz2[u] < sz2[v]) swap(u, v);
par2[v] = u;
sz2[u] += sz2[v];
}
array<int, 3> e[N], qq[N];
int w[N], ans[N];
vector<array<int, 3>> vals[N];
vector<array<int, 3>> ask[N];
bool bad[N];
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> e[i][1] >> e[i][2] >> e[i][0];
}
bad[m] = 1;
sort(e, e + m);
for (int i = 0; i < m; i++) {
w[i] = e[i][0];
}
int q;
cin >> q;
memset(ans, -1, sizeof ans);
vector<int> v;
int prv = 0;
auto process = [&] (int L, int R) {
for (int k = L; k <= R; k++) {
int t = qq[k][0];
if (t == 1) {
int b = qq[k][1], r = qq[k][2];
w[b] = r;
} else {
int x = qq[k][1], mx = qq[k][2];
int idx = lower_bound(e, e + m, (array<int, 3>) {mx, 0, 0}) - e;
if (idx < m) {
ask[idx].push_back({x, mx, k});
for (auto i : v) {
// cout << ">>> " << e[i][1] << ' ' << e[i][2] << '\n';
vals[k].push_back({e[i][1], e[i][2], w[i]});
}
}
}
}
for (int i = 1; i <= n; i++) {
par[i] = i;
sz[i] = 1;
par2[i] = sz2[i] = -1;
}
for (int i = m - 1; i >= 0; i--) {
if (!bad[i]) {
// cout << "> " << e[i][1] << ' ' << e[i][2] << " (" << e[i][0] << ")" << '\n';
join(e[i][1], e[i][2]);
}
for (auto [x, y, idx] : ask[i]) {
for (auto [U, V, c] : vals[idx]) {
if (c >= y) {
// if (idx == 2) {
// cout << ">> " << U << ' ' << V << ' ' << c << '\n';
// }
join2(U, V);
}
}
ans[idx] = sz2[find2(x)];
for (auto j : in) {
par2[j] = sz2[j] = -1;
}
in.clear();
}
ask[i].clear();
}
for (int k = L; k <= R; k++) {
vals[k].clear();
}
for (int i = 0; i < m; i++) {
e[i][0] = w[i];
}
sort(e, e + m);
for (int i = 0; i < m; i++) {
w[i] = e[i][0];
}
};
for (int k = 0; k < q; k++) {
ans[k] = -1;
if (v.size() == B) {
process(prv, k - 1);
for (auto i : v) {
bad[i] = 0;
}
v.clear();
prv = k;
}
cin >> qq[k][0] >> qq[k][1] >> qq[k][2];
int t = qq[k][0];
if (t == 1) {
qq[k][1]--;
int b = qq[k][1];
if (!bad[b]) {
bad[b] = 1;
v.push_back(b);
}
} else {
ans[k] = 1;
}
}
process(prv, q - 1);
for (auto i : ans) {
if (i == -1) continue;
cout << i << '\n';
}
return 0;
}
# | 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... |