#ifdef ONPC
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#ifndef ONPC
#pragma GCC target("avx")
#pragma GCC target("popcnt")
#define cerr if (false) cerr
#endif
using namespace std;
#define all(v) begin(v), end(v)
#define watch(x) cerr << #x << ": " << x << endl;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> Pint;
typedef pair<ll, ll> Pll;
mt19937_64 gen64(chrono::steady_clock::now().time_since_epoch().count());
inline ll rnd(ll l = LLONG_MIN, ll r = LLONG_MAX) {
return uniform_int_distribution<ll>(l, r)(gen64);
}
template<class T>
bool umin(T &a, const T &b) {
return (a > b ? a = b, true : false);
}
template<class T>
bool umax(T &a, const T &b) {
return (a < b ? a = b, true : false);
}
const int mod = 998244353;
ll mult(ll a, ll b) {
return (a * b) % mod;
}
template<class T>
void add(T &a, const T &b) {
a = (a + b) % mod;
}
const int inf = int(1e9) + 10;
const ll INF = ll(1e18) + 10;
const int maxn = 1e5 + 10, maxc = 10;
constexpr int sqn = sqrt(maxn) + 10;
struct DSU {
vector<int> p, w;
DSU(int n) : p(n + 1), w(n + 1, 1) {
iota(all(p), 0);
}
int leader(int v) {
return (p[v] == v ? v : p[v] = leader(p[v]));
}
bool unite(int v, int u) {
v = leader(v), u = leader(u);
if (v == u) {
return false;
}
if (w[v] < w[u]) {
swap(v, u);
}
p[u] = v;
w[v] += w[u];
return true;
}
void clear() {
fill(all(w), 1);
iota(all(p), 0);
}
};
struct edge {
int v = 0, u = 0, w = 0, t = 0;
};
bool operator<(edge a, edge b) {
return make_tuple(-a.w, a.t, a.v, a.u) < make_tuple(-b.w, b.t, b.v, b.u);
}
struct query {
int v = 0, w = 0, t = 0, tp = 0;
};
void solve() {
int n, m;
cin >> n >> m;
vector<edge> e(m);
for (auto &[v, u, w, t] : e) {
cin >> v >> u >> w; t = -1; v--, u--;
}
int q;
cin >> q;
vector<query> qrs(q);
for (int i = 0; i < q; ++i) {
auto &[v, w, t, tp] = qrs[i];
cin >> tp >> v >> w; v--;
t = i;
}
set<edge> s;
for (auto &r : e) {
s.insert(r);
}
vector<vector<Pint>> g(n);
vector<bool> used(n);
vector<int> ans(q);
vector<vector<edge>> upd(m);
for (int i = 0; i < m; ++i) {
upd[i].push_back(e[i]);
}
for (int bl = 0; bl * sqn < q; ++bl) {
int l = bl * sqn, r = min((bl + 1) * sqn, q);
vector<pair<edge, int>> buffer;
map<int, vector<int>> mp;
for (int i = l; i < r; ++i) {
if (qrs[i].tp == 1) {
int id = qrs[i].v;
if (s.count(e[id])) {
s.erase(e[id]);
}
e[id].w = qrs[i].w;
e[id].t = i;
upd[id].push_back(e[id]);
buffer.push_back({e[id], id});
} else {
mp[-qrs[i].w].push_back(i);
}
}
DSU dsu(n);
auto it = s.begin();
for (auto &[_w, qr] : mp) {
int w = _w * -1;
while (it != s.end() && it->w >= w) {
dsu.unite(it->v, it->u);
it++;
}
for (auto &id : qr) {
auto [v, w, t, tp] = qrs[id];
for (auto [_r, i] : buffer) {
auto rit = upper_bound(all(upd[i]), edge{0, 0, 0, t}, [](edge a, edge b) { return a.t < b.t; });
if (rit == upd[i].begin()) continue;
auto r = *prev(rit);
if (r.t <= t) {
int v = dsu.leader(r.v), u = dsu.leader(r.u);
if (v != u) {
g[v].push_back({u, r.w});
g[u].push_back({v, r.w});
}
}
}
queue<int> q;
q.push(dsu.leader(v));
used[dsu.leader(v)] = true;
while (!q.empty()) {
int v = q.front(); q.pop();
ans[t] += dsu.w[v];
for (auto [u, uw] : g[v]) {
if (w <= uw && !used[u]) {
used[u] = true;
q.push(u);
}
}
}
used[dsu.leader(v)] = false;
for (auto [_r, i] : buffer) {
auto rit = upper_bound(all(upd[i]), edge{0, 0, t, 0}, [](edge a, edge b) { return a.t < b.t; });
if (rit == upd[i].begin()) continue;
auto r = *prev(rit);
if (r.t <= t) {
int v = dsu.leader(r.v), u = dsu.leader(r.u);
if (v != u) {
g[v].clear();
g[u].clear();
used[v] = used[u] = false;
}
}
}
}
}
for (auto &[r, id] : buffer) {
s.insert(e[id]);
upd[id].clear();
}
dsu.clear();
}
for (int i = 0; i < q; ++i) {
if (qrs[i].tp == 2) {
cout << ans[i] << '\n';
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
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... |