Submission #848263

#	Time	Username	Problem	Language	Result	Execution time	Memory
848263		popovicirobert	Bridges (APIO19_bridges)	C++14	100 / 100	1779 ms	8352 KiB

bridges

#include <bits/stdc++.h>

#define lsb(x) (x & (-x))

using ull = unsigned long long;
using ll = long long;

using namespace std;


#ifdef HOME
    #define LOCAL_CHECK(x) assert(x);
#else
    #define LOCAL_CHECK(x)
#endif 

// https://judge.yosupo.jp/submission/159946

template<bool _CompressPath = true>
class DSU {
public:
    DSU(int n) : n(n) {
        LOCAL_CHECK(n > 0);

        link.resize(n, -1);
        size.resize(n, 1);
    }

    int getRoot(int x) noexcept {
        LOCAL_CHECK(0 <= x && x < n);

        if (_CompressPath) {
            return link[x] == -1 ? x : link[x] = getRoot(link[x]);
        } else {
            return link[x] == -1 ? x : getRoot(link[x]);
        }
    }

    bool join(int x, int y) noexcept(_CompressPath) {
        LOCAL_CHECK(0 <= x && x < n);
        LOCAL_CHECK(0 <= y && y < n);

        x = getRoot(x), y = getRoot(y);
        if (size[x] > size[y]) {
            std::swap(x, y);
        }

        bool joined = (x != y);
        if (joined) {
            link[x] = y;
            size[y] += size[x];
            if (!_CompressPath) {
                joinedLinks.push(x);
            }
        } else {
            if (!_CompressPath) {
                joinedLinks.push(-1);
            }
        }

        return joined;
    }

    inline int getSize(int x) noexcept {
        return size[getRoot(x)];
    }

    void undo() {
        static_assert(!_CompressPath);

        if (!joinedLinks.empty()) {
            auto lastJoin = joinedLinks.top();

            joinedLinks.pop();

            if (lastJoin == -1) return;

            size[link[lastJoin]] -= size[lastJoin];
            link[lastJoin] = -1;
        } else {
            assert(false);
        }
    }

private:
    std::vector<int> link;
    std::vector<int> size;
    int n;

    std::stack<int> joinedLinks;
};


struct Edge {
    int x, y, w;
};

struct Update {
    int edgeId;
    int w;
    int pos;
};

struct Query {
    int node;
    int w;
    int pos;
};


int main() {
#ifdef HOME
    ifstream cin("input.in");
    ofstream cout("output.out");
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

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

    vector<Edge> edges(m);
    for (auto& e : edges) {
        cin >> e.x >> e.y >> e.w;
    }


    vector<int> markedEdges(m, -1);
    vector<int> markedUpdatedEdges(m, -1);

    vector<int> edgeOrder(m);
    iota(edgeOrder.begin(), edgeOrder.end(), 0);

    DSU<false> dsu(n + 1);
    const int LIM = 3 * sqrt(n);

    int q;
    cin >> q;

    vector<int> result(q, -1);

    for (int qq = 0; qq < q; qq += LIM) {
        vector<Query> queries;
        vector<Update> updates;
        vector<int> currentEdges;

        for (int i = 0; i < q - qq && i < LIM; i++) {
            int t;
            cin >> t;
            if (t == 1) {
                int edgeId, w;
                cin >> edgeId >> w;
                edgeId--;
                updates.push_back({edgeId, w, i + qq});
                if (markedEdges[edgeId] != qq) {
                    currentEdges.push_back(edgeId);
                }
                markedEdges[edgeId] = qq;
            } else {
                int node, w;
                cin >> node >> w;
                queries.push_back({node, w, i + qq});
            }
        }

        sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
            return a.w > b.w;
        });

        sort(edgeOrder.begin(), edgeOrder.end(), [&](const int& a, const int& b) {
            return edges[a].w > edges[b].w;
        });

        int pos = 0;
        for (auto& query : queries) {
            while (pos < m && edges[edgeOrder[pos]].w >= query.w) {
                int edgeId = edgeOrder[pos];
                if (markedEdges[edgeId] != qq) {
                    dsu.join(edges[edgeId].x, edges[edgeId].y);
                }
                pos++;
            }

            static int currentIteration = -1;
            currentIteration++;

            int i = 0;
            while (i < (int)updates.size() && updates[i].pos <= query.pos) {
                i++;
            }

            i--;
            int j = 0;
            while (i >= 0) {
                int edgeId = updates[i].edgeId;
                if (markedUpdatedEdges[edgeId] != currentIteration) {
                    markedUpdatedEdges[edgeId] = currentIteration;
                    if (query.w <= updates[i].w) {
                        dsu.join(edges[edgeId].x, edges[edgeId].y);
                        j++;
                    }
                }
                i--;
            }

            for (auto edgeId : currentEdges) {
                if (markedUpdatedEdges[edgeId] != currentIteration && edges[edgeId].w >= query.w) {
                    dsu.join(edges[edgeId].x, edges[edgeId].y);
                    j++;
                }
            }

            result[query.pos] = dsu.getSize(query.node);

            while (j > 0) {
                dsu.undo();
                j--;
            }
        }

        for (int i = pos - 1; i >= 0; i--) {
            if (markedEdges[edgeOrder[i]] != qq) {
                dsu.undo();
            }
        }

        for (auto& update : updates) {
            edges[update.edgeId].w = update.w;
        }
    }

    for (auto itr : result) {
        if (itr != -1) {
            cout << itr << "\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