Submission #1124874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124874		Zero_OP	Bridges (APIO19_bridges)	C++17	100 / 100	1429 ms	125564 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

struct disjoint_set{
    struct state{
        int u, lu, v, lv;
        state(int u, int lu, int v, int lv) : u(u), lu(lu), v(v), lv(lv) {}
    };

    stack<state> states;
    vector<int> lab;
    disjoint_set(int n) : lab(n, -1) {}

    int root(int u){
        return lab[u] < 0 ? u : (root(lab[u]));
    }

    bool join(int u, int v){
        u = root(u);
        v = root(v);
        if(u == v) return false;
        if(lab[u] > lab[v]) swap(u, v);
        states.push(state(u, lab[u], v, lab[v]));
        lab[u] += lab[v];
        lab[v] = u;
        return true;
    }

    int snapshot(){ return (int)states.size(); }
    int get_size(int u){ return -lab[root(u)]; }
    void rollback(){
        assert(!states.empty());
        lab[states.top().u] = states.top().lu;
        lab[states.top().v] = states.top().lv;
        states.pop();
    }

    void reset(){
        fill(lab.begin(), lab.end(), -1);
        stack<state>().swap(states);
    }

    void rollback(int snp){
        while(snapshot() != snp){
            rollback();
        }
    }
};

struct edge{
    int u, v, d;
    edge() : u(u), v(v), d(d) {}
    edge(int u, int v, int d) : u(u), v(v), d(d) {}
    bool operator < (const edge& o){
        return d > o.d;
    }
};

const int MAX = 1e5 + 5;

int N, M, Q;
edge E[MAX];

int type[MAX], x[MAX], y[MAX];
vector<int> extra[MAX];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> N >> M;
    for(int i = 0; i < M; ++i){
        int u, v, d;
        cin >> u >> v >> d;
        --u, --v;
        E[i] = edge(u, v, d);
    }

    cin >> Q;
    for(int i = 0; i < Q; ++i){
        cin >> type[i] >> x[i] >> y[i];
        --x[i];
    }

    disjoint_set dsu(N);

    const int B = 1000;

    vector<bool> in_use(M);
    vector<int> ans(Q, -1);

    for(int l = 0; l < Q; l += B){
        int r = min(l + B, Q) - 1;

        vector<int> in_edges;
        vector<tuple<int, int, int>> queries;

        for(int i = l; i <= r; ++i){
            if(type[i] == 1){
                in_use[x[i]] = true;
            } else{
                queries.emplace_back(-y[i], x[i], i);
            }
        }

        vector<edge> out_edges;
        for(int i = 0; i < M; ++i){
            if(!in_use[i]){
                out_edges.push_back(E[i]);
            } else{
                in_edges.push_back(i);
            }
            in_use[i] = false;
        }

        sort(queries.begin(), queries.end());
        sort(out_edges.begin(), out_edges.end());

        for(int i = l; i <= r; ++i){
            if(type[i] == 1){
                E[x[i]].d = y[i];
            } else{
                for(auto id : in_edges){
                    if(E[id].d >= y[i]){
                        extra[i].emplace_back(id);
                    }
                }
            }
        }

        int i = 0;
        for(auto [limit, u, id] : queries){
            limit = -limit;
            while(i < (int)out_edges.size() && out_edges[i].d >= limit){
                dsu.join(out_edges[i].u, out_edges[i].v);
                ++i;
            }

            int snap = dsu.snapshot();
            for(auto id_e : extra[id]){
                dsu.join(E[id_e].u, E[id_e].v);
            }

            ans[id] = dsu.get_size(u);
            dsu.rollback(snap);
        }

        dsu.reset();
    }

    for(int i = 0; i < Q; ++i){
        if(ans[i] != -1) cout << ans[i] << '\n';
    }

    return 0;
}

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