Submission #1211417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211417		nrg_studio	Bridges (APIO19_bridges)	C++20	100 / 100	2487 ms	209024 KiB

bridges

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

#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define vec vector

class DSU {
    public:
    vec<int> par, sz;
    vec<pair<int&,int>> hist;

    DSU(int n) : par(n), sz(n,1) {iota(all(par),0);}
    int get(int x) {return par[x]==x ? x : get(par[x]);}
    void unite(int a, int b, bool c) {
        a = get(a); b = get(b);
        if (a==b) {return;}
        if (sz[a]<sz[b]) {swap(a,b);}
        if (c) {
            hist.pb({sz[a],sz[a]});
            hist.pb({par[b],par[b]});
        }
        par[b] = a; sz[a] += sz[b];
    }
    void rb() {
        while (hist.size()) {
            for (int i=0;i<2;i++) {
                hist.back().f = hist.back().s;
                hist.pop_back();
            }
        }
    }
    void reset() {
        hist.clear();
        fill(all(sz),1);
        iota(all(par),0);
    }
};

const int B = 500;
struct Edge {
    int u, v, w, id;
};

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

    int n, m; cin >> n >> m;
    vec<Edge> ed(m);
    for (int i=0;i<m;i++) {
        cin >> ed[i].u >> ed[i].v >> ed[i].w;
        ed[i].u--; ed[i].v--;
        ed[i].id = i;
    }

    int q; cin >> q;
    vec<Edge> qry(q); 
    vec<int> ans(q,-1);
    
    vec<bool> bad(m,false);
    vec<vec<int>> weights(q);

    vec<int> bad_idx, good_ed, good_qry;

    DSU dsu(n);

    for (int b=0;b<(q+B-1)/B;b++) {
        dsu.reset();
        bad_idx.clear(); good_ed.clear(); good_qry.clear();

        int l = b*B, r = min(q,b*B+B);
        for (int i=l;i<r;i++) {
            cin >> qry[i].u >> qry[i].v >> qry[i].w; qry[i].v--;
            qry[i].id = i;
            if (qry[i].u==1) {
                if (!bad[qry[i].v]) {bad_idx.pb(i);}
                bad[qry[i].v] = true;
            } else {good_qry.pb(i);}
        }
        for (int i=m-1;i>=0;i--) {
            if (!bad[i]) {good_ed.pb(i);}
        }
        sort(all(good_ed),[&](int a, int c) {return ed[a].w>ed[c].w;});
        sort(all(good_qry),[&](int a, int c) {return qry[a].w>qry[c].w;});

        for (int i : bad_idx) {weights[l].pb(i==l ? qry[i].w : ed[qry[i].v].w);}
        for (int i=l+1;i<r;i++) {
            for (int j=0;j<bad_idx.size();j++) {
                weights[i].pb((qry[i].u==1 && qry[i].v==qry[bad_idx[j]].v) ? qry[i].w : weights[i-1][j]);
            }
        }
        
        int ed_ptr = 0;
        for (int i : good_qry) {//cout<<i<<' ';
            while (ed_ptr<good_ed.size() && ed[good_ed[ed_ptr]].w>=qry[i].w) {
                int e = good_ed[ed_ptr];
                //cout << ed[e].u+1<<' '<<ed[e].v+1<<' '<<ed[e].w<<'\n';
                dsu.unite(ed[e].u,ed[e].v,false);
                ed_ptr++; 
            }
            for (int j=0;j<weights[i].size();j++) {
                if (weights[i][j]>=qry[i].w) {
                    int k = qry[bad_idx[j]].v;
                    //cout << ed[k].u+1<<' '<<ed[k].v+1<<'\n';
                    dsu.unite(ed[k].u,ed[k].v,true);
                }
            }
            ans[i] = dsu.sz[dsu.get(qry[i].v)];
            dsu.rb();
        }
        for (int j=0;j<bad_idx.size();j++) {
            ed[qry[bad_idx[j]].v].w = weights[r-1][j];
            bad[qry[bad_idx[j]].v] = false;
        }
    }
    for (int i=0;i<q;i++) {if (ans[i]!=-1) {cout << ans[i] << '\n';}}
}

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