Submission #997620

#	Time	Username	Problem	Language	Result	Execution time	Memory
997620		avighna	Bridges (APIO19_bridges)	C++17	13 / 100	780 ms	524288 KiB

bridges

#include <bits/stdc++.h>

typedef long long ll;

class UFDS {
public:
    std::vector<ll> par, sz;
    std::vector<std::pair<ll, ll>> rollback;

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

    ll root(ll x) {
        return x == par[x] ? x : root(par[x]);
    }

    void merge(ll x, ll y, bool should_rollback = false) {
        x = root(x);
        y = root(y);
        if (sz[x] > sz[y]) {
            std::swap(x, y);
        }
        if (should_rollback) {
            rollback.push_back({x, par[x]});
            rollback.push_back({y, sz[y]});
        }
        if (x != y) {
            par[x] = y;
            sz[y] += sz[x];
        }
    }

    void rollback_previous_change() {
        if (!rollback.empty()) {
            auto p1 = rollback.back();
            rollback.pop_back();
            auto p2 = rollback.back();
            rollback.pop_back();
            sz[p1.first] = p1.second;
            par[p2.first] = p2.second;
        }
    }
};

struct Edge {
    ll u, v, d;
};

struct Update {
    ll i;
    ll b, r;
};

struct Query {
    ll i;
    ll w, s;
};

const ll block_size = 317;
struct Block {
    std::vector<Update> updates;
    std::set<ll> tampered_with;
    std::vector<Update> in_block; // updates that happened in the block
    std::map<ll, std::pair<ll, ll>> latest_val; // {value, when}
    UFDS dsu;
    Block(ll n) : dsu(n) {}
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    ll n, m;
    std::cin >> n >> m;
    std::vector<Edge> edges(m);
    for (auto &edge : edges) {
        std::cin >> edge.u >> edge.v >> edge.d;
    }
    ll q;
    std::cin >> q;
    std::vector<Query> queries;
    std::vector<Block> blocks(block_size + 1, Block(n));
    for (auto &b : blocks) {
        for (ll i = 0; i < m; ++ i) {
            b.latest_val[i + 1] = {edges[i].d, -1};
        }
    }
    for (ll i = 0; i < q; ++ i) {
        ll type;
        std::cin >> type;
        if (type == 1) {
            Update u;
            std::cin >> u.b >> u.r;
            u.i = i;
            ll block_num = i / block_size;
            blocks[block_num].in_block.push_back(u);
            for (ll j = block_num + 1; j <= block_size; ++ j) {
                blocks[j].latest_val[u.b] = {u.r, i};
            }
        } else {
            Query q;
            std::cin >> q.s >> q.w;
            q.i = i;
            queries.push_back(q);
        }
    }
    for (auto &b : blocks) {
        for (ll i = 1; i <= m; ++ i) {
            b.updates.push_back({b.latest_val[i].second, i, b.latest_val[i].first});
        }
    }
    for (auto &b : blocks) {
        std::vector<Update> new_updates;
        for (auto &u : b.updates) {
            auto it = std::find_if(b.in_block.begin(), b.in_block.end(), [&u](const Update &v) {
                return u.b == v.b;
            });
            if (it == b.in_block.end()) {
                new_updates.push_back(u);
            } else {
                b.tampered_with.insert(u.b);
            }
        }
        b.updates = new_updates;
    }

    for (auto &b : blocks) {
        std::sort(b.updates.begin(), b.updates.end(), [](Update a, Update b) { return a.r < b.r; });
        std::sort(b.in_block.begin(), b.in_block.end(), [](Update a, Update b) { return a.i > b.i; });
    }
    std::sort(queries.begin(), queries.end(), [](Query a, Query b) { return a.w > b.w; });

    std::vector<ll> answers(q, -1);
    for (auto &q : queries) {
        for (auto &b : blocks) {
            while (!b.updates.empty() && b.updates.back().r >= q.w) {
                ll e = b.updates.back().b - 1;
                b.dsu.merge(edges[e].u, edges[e].v);
                b.updates.pop_back();
            }
        }
        auto &in_block = blocks[q.i / block_size].in_block;
        auto &dsu = blocks[q.i / block_size].dsu;
        auto st = blocks[q.i / block_size].tampered_with;
        auto latest_val = blocks[q.i / block_size].latest_val;
        std::set<ll> enc;
        for (auto &u : in_block) {
            if (u.i > q.i) {
                continue;
            }
            if (enc.count(u.b)) {
                continue;
            }
            enc.insert(u.b);
            latest_val[u.b] = {u.r, u.i};
        }
        ll num_merges = 0;
        for (auto &b : st) {
            if (latest_val[b].first >= q.w) {
                dsu.merge(edges[b - 1].u, edges[b - 1].v, true);
                num_merges++;
            }
        }
        answers[q.i] = dsu.sz[dsu.root(q.s)];
        for (ll i = 0; i < num_merges; ++ i) {
            dsu.rollback_previous_change();
        }
    }

    for (auto &i : answers) {
        if (i != -1) {
            std::cout << i << "\n";
        }
    }
}

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