Submission #405222

#	Time	Username	Problem	Language	Result	Execution time	Memory
405222		gevacrt	Bridges (APIO19_bridges)	C++17	13 / 100	3083 ms	291036 KiB

bridges

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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()

struct DISJOINT_SET_UNION {
    vi par, sz; int groups;
    void init(int N){
        par.resize(N), sz.resize(N, 1);
        for(int x = 0; x < N; x++) par[x] = x;
        groups = N;
    }

    int parent(int x){
        if(par[x] == x) return x;
        return parent(par[x]);
    }

    void merge(int x, int y){
        x = parent(x), y = parent(y);
        if(x == y) return;
        if(sz[x] > sz[y]) swap(x, y);
        par[x] = y; sz[y] += sz[x];
        groups--;
    }
    void unmerge(int x, int y){
        if(sz[x] > sz[y]) swap(x, y);
        par[x] = x; sz[y] -= sz[x];
        groups++;
    }
};

const int BLOCK = 450;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M; cin >> N >> M;

    vector<array<int, 3>> E(M+1); // {u, v, d}
    vi last_changed(M+1);
    for(int x = 1; x <= M; x++){
        cin >> E[x][0] >> E[x][1] >> E[x][2];
    }

    vector<array<int, 3>> QRY; // {weight, start, time}
    vector<array<int, 4>> UPD; // {d, l, r, x}

    int Q; cin >> Q;
    for(int t = 1; t <= Q; t++){
        int c; cin >> c;
        if(c == 1){
            int i, d; cin >> i >> d;
            UPD.push_back({E[i][2], last_changed[i], t-1, i});
            last_changed[i] = t; E[i][2] = d;

        }else{
            int s, w; cin >> s >> w;
            QRY.push_back({w, s, t});
        }
    }

    int BOQ = (Q/BLOCK)*BLOCK+BLOCK;
    for(int x = 1; x <= M; x++){
        UPD.push_back({E[x][2], last_changed[x], BOQ-1, x});
    }

    sort(all(QRY)); sort(all(UPD));
    reverse(all(QRY));

    DISJOINT_SET_UNION DSU[BLOCK];
    for(auto &i : DSU) i.init(N+1);

    vvi jp(BOQ+10); vi ans(Q+10, -1);

    auto upd = [&](int l, int r, int x){
        for(; l <= r; ){
            if(l%BLOCK == 0 and l+BLOCK-1 <= r){
                DSU[l/BLOCK].merge(E[x][0], E[x][1]);
                l += BLOCK;
            }else{
                jp[l].push_back(x); l++;
            }
        }
    };

    for(auto [weight, start, time] : QRY){
        while(!UPD.empty() and UPD.back()[0] >= weight){
            upd(UPD.back()[1], UPD.back()[2], UPD.back()[3]);
            UPD.pop_back();
        }

        // dsu with rollbacks
        vii rollback; auto &BOB = DSU[time/BLOCK];
        
        for(auto i : jp[time]){
            auto [u, v, _] = E[i];
            u = BOB.parent(u), v = BOB.parent(v);
            if(u == v) continue;
            BOB.merge(u, v); rollback.push_back({u, v});
        }

        ans[time] = BOB.sz[BOB.parent(start)];

        reverse(all(rollback));
        for(auto [u, v] : rollback)
            BOB.unmerge(u, v);
    }

    for(auto i : ans)
        if(i != -1) cout << i << "\n";

    return 0;
}

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