Submission #998267

#	Time	Username	Problem	Language	Result	Execution time	Memory
998267		avighna	Bridges (APIO19_bridges)	C++17	100 / 100	2495 ms	11152 KiB

bridges

#include <bits/stdc++.h>

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

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

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

    void merge(int x, int 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({x, par[x]});
            rollback.push({y, sz[y]});
        }
        if (x != y) {
            par[x] = y;
            sz[y] += sz[x];
        }
    }

    void rollback_all_changes() {
        while (!rollback.empty()) {
            auto p1 = rollback.top();
            rollback.pop();
            auto p2 = rollback.top();
            rollback.pop();
            sz[p1.first] = p1.second;
            par[p2.first] = p2.second;
        }
    }
};

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

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

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

const int block_size = 500;
struct Block {
    std::vector<Query> queries;
    std::vector<Update> in_block; // updates that happened in the block
};

class vector_with_rollbacks {
public:
    std::vector<std::pair<int, int>> m;

    std::stack<std::pair<int, int>> rollback;

    vector_with_rollbacks(int n) {
        m.resize(n);
    }

    void modify(int x, std::pair<int, int> y, bool should_rollback = false) {
        if (should_rollback) {
            rollback.push({x, x});
            rollback.push(m[x]);
        }
        m[x] = y;
    }

    void rollback_all_changes() {
        while (!rollback.empty()) {
            auto p1 = rollback.top();
            rollback.pop();
            auto p2 = rollback.top();
            rollback.pop();
            m[p2.first] = p1;
        }
    }
};

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

    int n, m;
    std::cin >> n >> m;
    std::vector<Edge> edges(m);
    for (auto &edge : edges) {
        std::cin >> edge.u >> edge.v >> edge.d;
    }
    int q;
    std::cin >> q;
    std::vector<Block> blocks(std::ceil(double(q) / block_size));
    for (int i = 0; i < q; ++ i) {
        int type;
        std::cin >> type;
        int block_num = i / block_size;
        if (type == 1) {
            Update u;
            std::cin >> u.b >> u.r;
            u.i = i;
            blocks[block_num].in_block.push_back(u);
        } else {
            Query q;
            std::cin >> q.s >> q.w;
            q.i = i;
            blocks[block_num].queries.push_back(q);
        }
    }
    while (!blocks.empty() && blocks.back().in_block.empty() && blocks.back().queries.empty()) {
        blocks.pop_back();
    }
    for (auto &b : blocks) {
        std::sort(b.in_block.begin(), b.in_block.end(), [](const Update &a, const Update &b) { return a.i < b.i; });
        std::sort(b.queries.begin(), b.queries.end(), [](const Query &a, const Query &b) { return a.w > b.w; });
    }

    std::vector<int> answers(q, -1);
    vector_with_rollbacks latest_val(m + 1); // {value, updated when}
    for (int i = 0; i < m; ++ i) {
        latest_val.modify(i + 1, {edges[i].d, -1});
    }
    for (auto &b : blocks) {
        std::vector<Update> updates;
        std::vector<bool> skip(m + 1);
        for (auto &u : b.in_block) {
            skip[u.b] = true;
        }
        for (int i = 1; i <= m; ++ i) {
            if (!skip[i]) {
                Update u = {latest_val.m[i].second, i, latest_val.m[i].first};
                updates.push_back(u);
            }
        }
        std::sort(updates.begin(), updates.end(), [](const Update &a, const Update &b) { return a.r < b.r; });
        UFDS dsu(n);
        for (auto &q : b.queries) {
            while (!updates.empty() && updates.back().r >= q.w) {
                int e = updates.back().b - 1;
                dsu.merge(edges[e].u, edges[e].v);
                updates.pop_back();
            }
            auto &in_block = blocks[q.i / block_size].in_block;
            for (auto &u : in_block) {
                if (u.i > q.i) {
                    continue;
                }
                latest_val.modify(u.b, {u.r, u.i}, true);
            }
            for (auto &_b : b.in_block) {
                auto b = _b.b;
                if (latest_val.m[b].first >= q.w) {
                    dsu.merge(edges[b - 1].u, edges[b - 1].v, true);
                }
            }
            answers[q.i] = dsu.sz[dsu.root(q.s)];
            dsu.rollback_all_changes();
            latest_val.rollback_all_changes();
        }
        for (auto &u : b.in_block) {
            latest_val.m[u.b] = {u.r, u.i};
        }
    }

    for (auto &i : answers) {
        if (i != -1) {
            std::cout << 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