Submission #172588

#	Time	Username	Problem	Language	Result	Execution time	Memory
172588		rama_pang	Bridges (APIO19_bridges)	C++14	14 / 100	2452 ms	10688 KiB

bridges

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

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) {
        if (root[n] == n) {
            return n;
        }
        return find(root[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;
    int 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;
    int weight;
    int 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<int> update(m, -1);
    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;

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

    for (int qi = 0; qi < q; qi += BLOCK) {
        vector<Query> query; // (time, start, weight)
        vector<tuple<int, int, int>> changed; // (id, weight, time)
        vector<Edge> unchanged;
        RollbackDSU DSU;
        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) {
                update[a] = b;
                changed.emplace_back(a, b, i);
            } else if (t == 2) {
                query.emplace_back(a, b, i);
            }
        }

        for (int i = 0; i < m; i++) {
            if (update[i] == -1) {
                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++) {
            while (j < unchanged.size() && unchanged[j].weight >= query[i].weight) {
                DSU.join(unchanged[j].u, unchanged[j].v);
                j++;
            }

            for (auto& c : changed) {
                int t, w, id;
                tie(id, w, t) = c;
                if (t <= query[i].time && w >= query[i].weight) {
                    DSU.join(edge[id].u, edge[id].v, true);
                } else if (t > query[i].time && edge[id].weight >= 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();
        }

        /* Update Original Edges */
        for (int i = 0; i < m; i++) {
            if (update[i] != -1) {
                edge[i].weight = update[i];
                update[i] = -1;
            }
        }
    }

    /* Answer Queries */
    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:127:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0, j = 0; i < query.size(); i++) {
                                ~~^~~~~~~~~~~~~~
bridges.cpp:128:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (j < unchanged.size() && unchanged[j].weight >= query[i].weight) {
                    ~~^~~~~~~~~~~~~~~~~~

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