Submission #172620

#	Time	Username	Problem	Language	Result	Execution time	Memory
172620		rama_pang	Bridges (APIO19_bridges)	C++14	100 / 100	2496 ms	7440 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
const int BLOCK = 850;

struct RollbackDSU {
    vector<int> root; // parent
    vector<int> sz; // size
    vector<pair<int, int>> operations; // (modified_id, size[id]). If size[id] == -1, then the parent changes

    void init(int n) {
        sz.assign(n, 1);
        root.assign(n, 0);
        iota(begin(root), end(root), 0);
    }

    int find(int n) {
        while (root[n] != n) {
            n = root[n];
        }
        return n;
    }

    bool join(int a, int b, bool revert = false) {
        a = find(a);
        b = find(b);
        if (a == b) {
            return false;
        }
        if (sz[a] < sz[b]) {
            swap(a, b);
        }
        if (revert) {
            operations.emplace_back(b, -1); // b's parent changes
            operations.emplace_back(a, sz[a]); // a's previous size
        }
        sz[a] += sz[b];
        root[b] = a;
        return true;
    }

    void rollback() {
        reverse(begin(operations), end(operations));
        for (auto& op : operations) {
            if (op.second == -1) {
                root[op.first] = op.first;
            } else {
                sz[op.first] = op.second;
            }
        }
        operations.clear();
    }
    
    int getSize(int n) {
        return sz[find(n)];
    }

};

struct Edge {
    int u, v, weight;
    Edge(int u, int v, int w) : u(u), v(v), weight(w) {}
    bool operator<(const Edge& o) const {
        return weight > o.weight;
    }
};

struct Query {
    int start, weight, time;
    Query(int s, int w, int t) : start(s), weight(w), time(t) {}
    bool operator<(const Query& o) const {
        return weight > o.weight;
    }
};

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

    int n, m;
    cin >> n >> m;

    vector<Edge> edge;
    vector<pair<int, int>> update(m, make_pair(-1, -1)); // (weight, update_time)

    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        edge.emplace_back(u, v, w);
    }

    int q;
    cin >> q;

    RollbackDSU DSU;
    vector<pair<int, int>> ans; // (time, answer)

    for (int qi = 0; qi < q; qi += BLOCK) {
        vector<Query> query; // query: (time, start, weight)
        vector<tuple<int, int, int, int>> changed; // (id, weight, time1, time2) -> the id-th edge has weight for time peirod [time1, time2]
        vector<Edge> unchanged; // ids of unchanged edges

        DSU.init(n);

        for (int i = qi; i < qi + BLOCK && i < q; i++) {
            int t, a, b;
            cin >> t >> a >> b;
            a--;

            if (t == 1) {
                if (update[a] == make_pair(-1, -1)) {
                    update[a].first = edge[a].weight;
                }
                changed.emplace_back(a, update[a].first, update[a].second, i - 1); // the current weight lasts between (t1, t2)
                update[a] = {b, i};
            } else if (t == 2) {
                query.emplace_back(a, b, i);
            }
        }

        for (int i = 0; i < m; i++) {
            if (update[i] != make_pair(-1, -1)) {
                changed.emplace_back(i, update[i].first, update[i].second, qi + BLOCK);

                // Update original edge's weight with latest update
                edge[i].weight = update[i].first;
                update[i] = make_pair(-1, -1);
            } else {
                unchanged.emplace_back(edge[i]);
            }
        }

        sort(begin(unchanged), end(unchanged));
        sort(begin(query), end(query));

        for (int i = 0, j = 0; i < query.size(); i++) { // O(BLOCK) iterations
            while (j < unchanged.size() && unchanged[j].weight >= query[i].weight) {
                DSU.join(unchanged[j].u, unchanged[j].v);
                j++;
            }

            for (auto& c : changed) { // O(BLOCK log n)
                int id, w, t1, t2;
                tie(id, w, t1, t2) = c;
                if (t1 <= query[i].time && query[i].time <= t2 && w >= query[i].weight) {
                    DSU.join(edge[id].u, edge[id].v, true);
                }
            }

            ans.emplace_back(query[i].time, DSU.getSize(query[i].start));
            DSU.rollback();
        }
    }


    sort(begin(ans), end(ans));
    for (auto& i : ans) {
        cout << i.second << "\n";
    }

    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:136:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0, j = 0; i < query.size(); i++) { // O(BLOCK) iterations
                                ~~^~~~~~~~~~~~~~
bridges.cpp:137:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (j < unchanged.size() && unchanged[j].weight >= query[i].weight) {
                    ~~^~~~~~~~~~~~~~~~~~

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