| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 357864 | shivensinha4 | 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")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,tune=native")
#include "bits/stdc++.h"
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'
class UFDS {
public:
vi p, rank, sz; int count = 0;
void build(int n) {
p.assign(n, 0); rank.assign(n, 0); sz.assign(n, 1);
for_(i, 0, n) p[i] = i;
count = n;
}
int getParent(int i) {
return (p[i] == i) ? i : (p[i] = getParent(p[i]));
}
void join(int i, int j) {
int a = getParent(i), b = getParent(j);
if (a == b) return;
count -= 1;
if (rank[a] > rank[b]) {
p[b] = a;
sz[a] += sz[b];
} else {
p[a] = b;
if (rank[a] == rank[b]) rank[b] += 1;
sz[b] += sz[a];
}
}
};
const int bs = 800;
int main() {
#ifdef mlocal
freopen("test.in", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m; cin >> n >> m;
vector<vector<int>> edge(m, vector<int>(2)); // {a, b, w}
vector<ll> wt(m);
for_(i, 0, m) {
cin >> edge[i][0] >> edge[i][1] >> wt[i];
edge[i][0] -= 1; edge[i][1] -= 1;
}
int q; cin >> q;
vector<vector<ll>> qr(q, vector<ll>(3)); // {for car: {type (2), weight, node}
for_(i, 0, q) {
cin >> qr[i][0] >> qr[i][1] >> qr[i][2];
qr[i][1] -= 1;
if (qr[i][0] == 2) swap(qr[i][1], qr[i][2]);
}
vector<bool> change(m, false);
UFDS ufds;
vector<pair<ll, int>> same;
int pt = 0;
vector<vi> adj(n);
vi adjChange(n), changed, lastSeen(n, -1);
vector<ll> currWt(m);
vector<vector<vector<ll>>> carQr;
for_(qq, 0, q) {
if ((qq % bs) == 0) carQr.push_back({});
if (qr[qq][0] == 2) carQr[carQr.size()-1].push_back({qr[qq][1], qq});
}
for_(i, 0, carQr.size()) sort(carQr[i].begin(), carQr[i].end(), greater<>());
int bpt = 0;
vi fin(q, -1);
for (auto &b: carQr) {
int bStart = bpt*bs;
if (b.size()) {
pt = 0;
ufds.build(n); same.clear(); changed.clear(); change.assign(m, false);
for_(i, bStart, min(q, bStart+bs)) if (qr[i][0] == 1) change[qr[i][1]] = true;
for_(i, 0, m) {
if (!change[i]) same.push_back({wt[i], i});
else changed.push_back(i);
}
sort(same.begin(), same.end(), greater<>());
for (auto &car: b) {
int qq = car[1];
while (pt < same.size() and same[pt].first >= qr[qq][1]) {
ufds.join(edge[same[pt].second][0], edge[same[pt].second][1]);
pt++;
}
for (auto &e: changed) currWt[e] = wt[e];
for_(i, bStart, qq) if (qr[i][0] == 1) currWt[qr[i][1]] = qr[i][2];
for (auto &e: changed) {
if (currWt[e] < qr[qq][1]) continue;
int c1 = ufds.getParent(edge[e][0]), c2 = ufds.getParent(edge[e][1]);
if (c1 == c2) continue;
if (adjChange[c1] != qq) {
adjChange[c1] = qq;
adj[c1].clear();
}
if (adjChange[c2] != qq) {
adjChange[c2] = qq;
adj[c2].clear();
}
adj[c1].push_back(c2); adj[c2].push_back(c1);
}
int cp = ufds.getParent(qr[qq][2]);
ll ans = ufds.sz[cp];
queue<int> qu;
lastSeen[cp] = qq;
qu.push(cp);
while (qu.size()) {
int p = qu.front(); qu.pop();
if (adjChange[p] == qq) for (auto i: adj[p]) {
if (lastSeen[i] == qq) continue;
lastSeen[i] = qq;
qu.push(i);
ans += ufds.sz[i];
}
}
fin[qq] = ans;
}
}
for_(i, bStart, min((bpt+1)*bs, q)) if (qr[i][0] == 1) wt[qr[i][1]] = qr[i][2];
bpt++;
}
for (auto i: fin) if (i != -1) cout << i << endl;
return 0;
}