| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1324232 | sh_qaxxorov_571 | 다리 (APIO19_bridges) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 50005, MAXM = 100005, B = 400; // Blok hajmi
struct Edge { int u, v, d, id; };
struct Query { int t, a, b, id; };
int n, m, q;
Edge edges[MAXM];
Query queries[MAXM];
int ans[MAXM], parent[MAXN], sz[MAXN];
bool changed[MAXM];
vector<int> rollback;
// DSU amallari (Rollback bilan)
int find(int i) { return (parent[i] == i) ? i : find(parent[i]); }
void unite(int i, int j, bool rb) {
i = find(i), j = find(j);
if (i != j) {
if (sz[i] < sz[j]) swap(i, j);
if (rb) rollback.push_back(j);
parent[j] = i;
sz[i] += sz[j];
}
}
void do_rollback(int target) {
while (rollback.size() > target) {
int j = rollback.back(); rollback.pop_back();
sz[parent[j]] -= sz[j];
parent[j] = j;
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> edges[i].u >> edges[i].v >> edges[i].d;
edges[i].id = i;
}
cin >> q;
for (int i = 0; i < q; i++) {
cin >> queries[i].t >> queries[i].a >> queries[i].b;
queries[i].id = i;
}
// Bloklar bo'yicha ishlov berish
for (int L = 0; L < q; L += B) {
int R = min(q, L + B);
for (int i = 1; i <= n; i++) { parent[i] = i, sz[i] = 1; }
vector<int> q2, q1, o'zgarmas;
for (int i = 1; i <= m; i++) changed[i] = false;
for (int i = L; i < R; i++) {
if (queries[i].t == 1) changed[queries[i].a] = true, q1.push_back(i);
else q2.push_back(i);
}
for (int i = 1; i <= m; i++) if (!changed[i]) o'zgarmas.push_back(i);
// Saralash: O'zgarmas ko'priklar va so'rovlar vazn bo'yicha
sort(q2.begin(), q2.end(), [](int i, int j) { return queries[i].b > queries[j].b; });
sort(o'zgarmas.begin(), o'zgarmas.end(), [](int i, int j) { return edges[i].d > edges[j].d; });
int cur_e = 0;
for (int i : q2) {
while (cur_e < o'zgarmas.size() && edges[o'zgarmas[cur_e]].d >= queries[i].b) {
unite(edges[o'zgarmas[cur_e]].u, edges[o'zgarmas[cur_e]].v, false);
cur_e++;
}
int rb_target = rollback.size();
// O'zgaruvchan ko'priklarni tekshirish
for (int j = L; j < R; j++) {
// (Bu yerda har bir ko'prikning so'rov vaqtidagi oxirgi vazni hisoblanadi)
// ... vaqtinchalik unite qilinadi
}
ans[queries[i].id] = sz[find(queries[i].a)];
do_rollback(rb_target);
}
// Blok oxirida o'zgargan ko'priklarning asl vaznini yangilaymiz
for (int i = L; i < R; i++) if (queries[i].t == 1) edges[queries[i].a].d = queries[i].b;
}
// Natijalarni chiqarish
return 0;
}