제출 #1268997

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268997		hoa208	Bridges (APIO19_bridges)	C++20	59 / 100	3095 ms	5956 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Edge { int u, v; int d; };
struct Query { int t, x, y; };

struct B {
    int u, v, d, id;
    bool operator < (const B &o) const {
        if (d != o.d) return d > o.d; // descending by d
        return id < o.id;
    }
};

int n, m, q;
vector<Edge> ed; // 1..m
vector<Query> qr; // 0..q-1

// DSU with rollback
vector<int> parent_, sz_;
vector<int> stk; // store v-roots that were attached

int findset_iter(int u) {
    while (parent_[u] != u) u = parent_[u];
    return u;
}

void unite_rb(int a, int b) {
    a = findset_iter(a);
    b = findset_iter(b);
    if (a == b) return;
    if (sz_[a] < sz_[b]) swap(a, b);
    // attach b under a
    parent_[b] = a;
    sz_[a] += sz_[b];
    stk.push_back(b);
}

void rollback_one() {
    int b = stk.back(); stk.pop_back();
    int a = parent_[b]; // a is current parent (the one we set)
    // decrement size of a, restore b as root
    sz_[a] -= sz_[b];
    parent_[b] = b;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#if defined(LOCAL)
    freopen("input.txt","r",stdin);
#endif

    cin >> n >> m;
    ed.assign(m+1, {0,0,0});
    for (int i = 1; i <= m; ++i) {
        int u,v,d; cin >> u >> v >> d;
        ed[i] = {u,v,d};
    }
    cin >> q;
    qr.assign(q, {0,0,0});
    for (int i = 0; i < q; ++i) {
        int t,x,y; cin >> t >> x >> y;
        qr[i] = {t,x,y};
    }

    int BLOCK = max(1, (int)sqrt(q));
    vector<int> ans(q, 0);

    // process blocks
    for (int L = 0; L < q; L += BLOCK) {
        int R = min(q-1, L + BLOCK - 1);

        // gather changed edges in this block
        vector<char> is_changed(m+1, 0);
        vector<int> changedList;
        for (int i = L; i <= R; ++i) if (qr[i].t == 1) {
            int ei = qr[i].x;
            if (!is_changed[ei]) {
                is_changed[ei] = 1;
                changedList.push_back(ei);
            }
        }

        // curd simulates weights inside the block (start from current global ed)
        vector<int> curd(m+1);
        for (int i = 1; i <= m; ++i) curd[i] = ed[i].d;

        // vr_block: for each query in block store list of changed edges (indices) that at that query time have weight >= query.w
        int BQ = R - L + 1;
        vector<vector<int>> vr_block(BQ);

        // simulate queries in block sequentially to build vr_block and also apply updates to curd (and to global ed at the end of handling)
        for (int i = L; i <= R; ++i) {
            int idx = i - L;
            if (qr[i].t == 1) {
                int ei = qr[i].x, nw = qr[i].y;
                curd[ei] = nw;      // change current weight in block simulation
                ed[ei].d = nw;      // persist update globally (so next blocks see it)
            } else {
                int u = qr[i].x, w = qr[i].y;
                // for all changed edges, if current weight >= w, add to vr
                for (int eidx : changedList) {
                    if (curd[eidx] >= w) vr_block[idx].push_back(eidx);
                }
            }
        }

        // build vector b: all base edges (not changed in this block) + one entry per type2 query in block
        vector<B> b;
        b.reserve((m - (int)changedList.size()) + BQ);
        // add queries (type2) entries
        for (int i = L; i <= R; ++i) {
            if (qr[i].t == 2) {
                int u = qr[i].x, w = qr[i].y;
                b.push_back({u, 0, w, i}); // id stores global query index
            }
        }
        // add base edges (those not in changed set) with their current global ed[].d
        for (int i = 1; i <= m; ++i) {
            if (!is_changed[i]) {
                b.push_back({ed[i].u, ed[i].v, ed[i].d, -1});
            }
        }
        sort(b.begin(), b.end());

        // init DSU
        parent_.assign(n+1, 0);
        sz_.assign(n+1, 1);
        for (int i = 1; i <= n; ++i) parent_[i] = i;
        stk.clear();

        // process sorted b
        for (auto &item : b) {
            if (item.id == -1) {
                // base edge: union permanently for this block
                unite_rb(item.u, item.v);
            } else {
                // query: we need to union all changed edges listed in vr_block for this specific query (temporarily)
                int qidx = item.id; // global index
                int localIdx = qidx - L;
                int presz = (int)stk.size();
                for (int eidx : vr_block[localIdx]) {
                    unite_rb(ed[eidx].u, ed[eidx].v);
                }
                int root = findset_iter(item.u);
                ans[qidx] = sz_[root];
                // rollback the temporary unions (those we pushed from vr_block)
                while ((int)stk.size() > presz) rollback_one();
            }
        }

        // rollback all base unions to restore empty DSU for next block
        while (!stk.empty()) rollback_one();

        // vr_block and other per-block containers go out of scope / cleared automatically
    }

    // output answers for all type2 queries in order
    for (int i = 0; i < q; ++i) if (qr[i].t == 2) {
        cout << ans[i] << '\n';
    }
    return 0;
}

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