| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 292055 | kajebiii | 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.
// Comment(Offline, MST, Sqrt)
#include <bits/stdc++.h>
using namespace std;
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
using ll = long long;
using pi = pair<int, int>;
const int INF = 0x3f3f3f3f;
const ll LINF = 1ll * INF * INF;
using ti = tuple<int, int, int>;
using qi = tuple<int, int, int, int>;
const int MAX_N = 5e4 + 100;
const int MAX_N = 1e5 + 100;
const int ROOT = 250;
struct UF {
int UNF[MAX_N], S[MAX_N], R[MAX_N];
stack<qi> stk;
void init(int n) {
for(int i=0; i<n; i++) UNF[i] = i, S[i] = 1, R[i] = 0;
while(!stk.empty()) stk.pop();
}
int find(int v) {
if(UNF[v] == v) return v;
return find(UNF[v]);
}
void merge(int a, int b, bool use) {
a = find(a), b = find(b);
if(a == b) return;
if(R[a] > R[b]) swap(a, b);
if(use) stk.emplace(1, a, b, UNF[a]);
UNF[a] = b;
S[b] = S[a] + S[b];
if(R[a] == R[b]) {
R[b] = R[b] + 1;
if(use) stk.emplace(2, -1, b, -1);
}
}
void rollback() {
while(!stk.empty()) {
int t, a, b, v; tie(t, a, b, v) = stk.top(); stk.pop();
if(t == 1) {
UNF[a] = v;
S[b] = S[b] - S[a];
}else{
R[b] = R[b] - 1;
}
}
}
};
int N, M, Q;
vector<qi> Ls;
vector<ti> Qs;
int Ans[MAX_Q];
int main() {
cin >> N >> M;
for(int i=0; i<M; i++) {
int x, y, c; scanf("%d%d%d", &x, &y, &c);
x--; y--;
Ls.emplace_back(c, x, y, i);
}
cin >> Q;
for(int i=0; i<Q; i++) {
int t, x, y; scanf("%d%d%d", &t, &x, &y);
x = x-1;
Qs.emplace_back(t, x, y);
}
UF uf;
vector<qi> ls;
vector<int> rev(M, 0);
vector<int> change(M, -1);
for(int r=0; r<(Q+ROOT-1)/ROOT; r++) {
int ql = r*ROOT, qr = min((r+1)*ROOT, Q);
ls = Ls;
sort(ALL(ls), [](qi &a, qi &b) { return get<0>(a) > get<0>(b);});
for(int i=0; i<M; i++) rev[get<3>(ls[i])] = i;
vector<int> edIx;
for(int i=0; i<M; i++) change[i] = -1;
for(int q=ql; q<qr; q++) {
int t, x, y; tie(t, x, y) = Qs[q];
if(t == 1) {
if(change[x] == -1) {
change[x] = SZ(edIx);
edIx.push_back(x);
}
}
}
vector<int> current(SZ(edIx), 0);
for(int i=0; i<SZ(edIx); i++) current[i] = get<0>(Ls[edIx[i]]);
vector<pair<int, vector<int>>> adds;
for(int q=ql; q<qr; q++) {
int t, x, y; tie(t, x, y) = Qs[q];
if(t == 1) {
current[change[x]] = y;
}else{
adds.emplace_back(q, current);
}
}
sort(ALL(adds), [](auto &a, auto &b) { return get<2>(Qs[a.one]) > get<2>(Qs[b.one]); });
int unchangeIx = 0;
uf.init(N);
for(auto vv: adds) {
int q; vector<int> ed; tie(q, ed) = vv;
int st, w; tie(ignore, st, w) = Qs[q];
while(unchangeIx < SZ(ls) && get<0>(ls[unchangeIx]) >= w) {
int c, x, y, ix; tie(c, x, y, ix) = ls[unchangeIx++];
if(change[ix] != -1) continue;
uf.merge(x, y, false);
}
for(int i=0; i<SZ(ed); i++) {
if(ed[i] >= w) {
int x, y; tie(ignore, x, y, ignore) = Ls[edIx[i]];
uf.merge(x, y, true);
}
}
Ans[q] = uf.S[uf.find(st)];
uf.rollback();
}
for(int q=ql; q<qr; q++) {
int t, x, y; tie(t, x, y) = Qs[q];
if(t == 1) {
get<0>(Ls[x]) = y;
}
}
}
for(int i=0; i<Q; i++) {
int t; tie(t, ignore, ignore) = Qs[i];
if(t == 2) printf("%d\n", Ans[i]);
}
return 0;
}