Submission #950048

#	Time	Username	Problem	Language	Result	Execution time	Memory
950048		efishel	Bridges (APIO19_bridges)	C++17	100 / 100	2511 ms	18332 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;

const ll MAXN = 5E4+16, SQRT = 700;

struct Edge { ll u, v, w, id; };
struct Query { ll qu, w, id, time; };
struct Update { ll edgId, w, time; };

struct DSU { // with rollback
    stack <ll> stku, stkv;
    vll par;
    vll sz;

    DSU (ll n): par(n), sz(n, 1) {
        iota(par.begin(), par.end(), 0);
    }

    ll find (ll u) { // log(n)
        return (u == par[u] ? u : find(par[u]));
    }

    void join (ll u, ll v) { // log(n)
        u = find(u);
        v = find(v);
        if (sz[u] > sz[v]) swap(u, v); // IMPORTANT: small to large to guarantee log(n) find
        assert(sz[u] <= sz[v]);
        assert(u == par[u]);
        assert(v == par[v]);
        stku.push(u);
        stkv.push(v);
        if (u == v) return;
        // join u to v
        par[u] = v;
        sz[v] += sz[u];
    }

    void rollback () {
        assert(stku.size());
        ll u = stku.top(); stku.pop();
        ll v = stkv.top(); stkv.pop();
        if (u == v) return;
        par[u] = u;
        sz[v] -= sz[u];
    }
};

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n, m;
    cin >> n >> m;
    vector <Edge> egs(m);
    {ll c = 0;
    for (auto &[u, v, w, id] : egs) { cin >> u >> v >> w; u--; v--; id = c++; }}
    ll Q;
    cin >> Q;
    vector <Query> qs;
    vector <Update> ups;
    vector <bool> isQry(Q);
    vll where(Q, -15);
    {ll qsid = 0;
    for (ll time = 0; time < Q; time++) {
        char type;
        cin >> type;
        switch (type) {
            case '1':
            ll edgId, newW;
            cin >> edgId >> newW;
            edgId--;
            ups.push_back({ edgId, newW, time });
            isQry[time] = false;
            where[time] = ups.size()-1;
            break;
            case '2':
            ll qu, w;
            cin >> qu >> w;
            qu--;
            qs.push_back({ qu, w, qsid, time });
            isQry[time] = true;
            where[time] = qs.size()-1;
            qsid++;
            break;
        }
    }}
    assert(*min_element(where.begin(), where.end()) != -15);
    vll vans(qs.size(), -15);
    vll upsVis(m, -16);
    for (ll i = 0; i < Q; i += SQRT) {
        vector <Query> qsblock;
        vector <Update> upsblock;
        vll involved;
        for (ll j = i; j < i+SQRT && j < Q; j++) {
            ll idx = where[j];
            if (isQry[j]) {
                qsblock.push_back(qs[idx]);
            } else {
                upsblock.push_back(ups[idx]);
                involved.push_back(ups[idx].edgId);
            }
        }
        sort(involved.begin(), involved.end());
        reverse(upsblock.begin(), upsblock.end());
        for (ll i : involved) {
            auto [u, v, w, id] = egs[i];
            upsblock.push_back({ id, w, -1 });
        }
        sort(qsblock.begin(), qsblock.end(), [&](const Query &a, const Query &b) {
            return a.w > b.w;
        });
        vector <Edge> sorted = egs;
        sort(sorted.begin(), sorted.end(), [&](const Edge &a, const Edge &b) {
            return a.w > b.w;
        });
        ll sortedi = 0;
        DSU dsu(n);
        auto addSorted = [&]() {
            auto [u, v, w, id] = sorted[sortedi];
            sortedi++;
            if (!binary_search(involved.begin(), involved.end(), id)) dsu.join(u, v);
        };
        ll toRollback = 0;
        auto addInvolved = [&](Update up, ll qtime, ll qw) {
            auto [edgId, w, time] = up;
            if (time > qtime) return; // happened later
            if (upsVis[edgId] == qtime) return; // newer version already effectuated
            upsVis[edgId] = qtime;
            auto [u, v, _, _2] = egs[edgId];
            if (qw > w) return;
            // add it
            dsu.join(u, v);
            toRollback++;
        };
        auto ans = [&](ll u) {
            return dsu.sz[dsu.find(u)];
        };
        for (auto [u, w, id, time] : qsblock) {
            while (sortedi < m && sorted[sortedi].w >= w) addSorted();
            for (Update up : upsblock) addInvolved(up, time, w); // IMPORTANT: reverse order
            vans[id] = ans(u);
            for (ll i = 0; i < toRollback; i++) dsu.rollback();
            toRollback = 0;
        }
        // prepare next block
        reverse(upsblock.begin(), upsblock.end()); // revert to original chronological order
        for (auto [edgId, w, time] : upsblock) {
            egs[edgId].w = w;
        }
    }
    assert(*min_element(vans.begin(), vans.end()) != -15);
    for (ll i : vans) cout << 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