Submission #1312911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312911		thuhienne	Bridges (APIO19_bridges)	C++17	30 / 100	3094 ms	8532 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

const int maxn = 50005;
const int maxq = 100005;
const int sz = 400; // Block size thu?ng d? 400-1000 cho N=5e4

struct Edge {
    int u, v, d, id;
};

struct Query {
    int op, a, b, id;
};

int n, m, q;
Edge edges[maxn], ori[maxn];
Query queries[maxq];
int ans[maxq];
bool is_changed[maxn];
int parent[maxn], sz_dsu[maxn];
vector<int> changed_edges;

struct RollbackInfo {
    int u, v, prev_sz_v;
};
vector<RollbackInfo> history;

int find(int i) {
    while (i != parent[i]) i = parent[i];
    return i;
}

void unite(int u, int v) {
    u = find(u); v = find(v);
    if (u == v) return;
    if (sz_dsu[u] > sz_dsu[v]) swap(u, v);
    history.push_back({u, v, sz_dsu[v]});
    parent[u] = v;
    sz_dsu[v] += sz_dsu[u];
}

void rollback(int target_size) {
    while (history.size() > target_size) {
        RollbackInfo last = history.back();
        history.pop_back();
        parent[last.u] = last.u;
        sz_dsu[last.v] = last.prev_sz_v;
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> ori[i].u >> ori[i].v >> ori[i].d;
        ori[i].id = i;
    }
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> queries[i].op >> queries[i].a >> queries[i].b;
        queries[i].id = i;
    }

    for (int l = 1; l <= q; l += sz) {
        int r = min(q, l + sz - 1);
        
        // Reset DSU
        for (int i = 1; i <= n; i++) { parent[i] = i, sz_dsu[i] = 1; }
        history.clear();
        changed_edges.clear();
        memset(is_changed, 0, sizeof(is_changed));

        vector<Query> ask;
        vector<int> update_indices;

        for (int i = l; i <= r; i++) {
            if (queries[i].op == 1) {
                is_changed[queries[i].a] = true;
                update_indices.push_back(i);
            } else {
                ask.push_back(queries[i]);
            }
        }

        // Danh sách c?nh không b? d?i trong block này
        vector<Edge> fixed_edges;
        for (int i = 1; i <= m; i++) {
            if (!is_changed[i]) fixed_edges.push_back(ori[i]);
            else changed_edges.push_back(i);
        }

        // S?p x?p truy v?n và c?nh c? d?nh gi?m d?n
        sort(ask.begin(), ask.end(), [](Query a, Query b) { return a.b > b.b; });
        sort(fixed_edges.begin(), fixed_edges.end(), [](Edge a, Edge b) { return a.d > b.d; });

        int pt = 0;
        for (auto &q_now : ask) {
            // 1. Thêm các c?nh c? d?nh d? tr?ng t?i
            while (pt < fixed_edges.size() && fixed_edges[pt].d >= q_now.b) {
                unite(fixed_edges[pt].u, fixed_edges[pt].v);
                pt++;
            }

            // 2. Luu tr?ng thái DSU tru?c khi thêm c?nh "t?m th?i"
            int snapshot = history.size();

            // 3. X? lý các c?nh b? s?a
            for (int edge_idx : changed_edges) {
                // Tìm tr?ng s? m?i nh?t c?a c?nh này tru?c/t?i th?i di?m q_now.id
                int current_w = ori[edge_idx].d;
                for (int u_idx : update_indices) {
                    if (u_idx < q_now.id && queries[u_idx].a == edge_idx) {
                        current_w = queries[u_idx].b;
                    }
                }
                if (current_w >= q_now.b) {
                    unite(ori[edge_idx].u, ori[edge_idx].v);
                }
            }

            ans[q_now.id] = sz_dsu[find(q_now.a)];
            
            // 4. Rollback v? snapshot (ch? xóa các c?nh t?m th?i)
            rollback(snapshot);
        }

        // C?p nh?t l?i m?ng ori sau khi h?t block
        for (int i = l; i <= r; i++) {
            if (queries[i].op == 1) {
                ori[queries[i].a].d = queries[i].b;
            }
        }
    }

    for (int i = 1; i <= q; i++) {
        if (queries[i].op == 2) cout << ans[i] << "\n";
    }
    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 16
• Subtask 3: 17 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27