제출 #711600

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
711600		Cyanmond	Collapse (JOI18_collapse)	C++17	35 / 100	15102 ms	401984 KiB

collapse

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include "collapse.h"
#include <bits/stdc++.h>

constexpr int inf = 1 << 30;

struct PPUnionFind {
    int n;
    std::vector<int> data, time;
    std::vector<int> compS;

    PPUnionFind(int n_) : n(n_) {
        data.assign(n, -1);
        time.assign(n, inf);
    }

    int find(int v, int t) {
        if (time[v] > t) return v;
        return find(data[v], t);
    }

    void merge(int a, int b, int t) {
        a = find(a, t);
        b = find(b, t);
        if (a == b) return;
        if (data[a] > data[b]) std::swap(a, b);
        data[a] += data[b];
        data[b] = a;
        time[b] = t;
        compS.push_back(t);
    }

    int countComp(int t) {
        auto itr = std::upper_bound(compS.begin(), compS.end(), t);
        return n - (int)(itr - compS.begin());
    }

    void reset() {
        compS.clear();
        data.assign(n, -1);
        time.assign(n, inf);
    }
};

constexpr int B = 600;

std::vector<int> simulateCollapse(int N, std::vector<int> T, std::vector<int> X, std::vector<int> Y,
                                  std::vector<int> W, std::vector<int> P) {
    const int C = (int)T.size(), Q = (int)P.size();
    for (int i = 0; i < C; ++i) {
        if (X[i] > Y[i]) {
            std::swap(X[i], Y[i]);
        }
    }
    std::vector<int> answer(Q);
    const int blocks = (C + B - 1) / B;
    std::vector<std::set<std::pair<int, int>>> alEdgesVec(blocks);
    for (int l = 0; l < C; l += B) {
        const int r = std::min(l + B, C);
        // [l, r)

        // build Union Find
        std::set<std::pair<int, int>> alEdges;
        for (int i = 0; i < l; ++i) {
            const auto p = std::make_pair(X[i], Y[i]);
            if (alEdges.find(p) == alEdges.end()) alEdges.insert(p);
            else alEdges.erase(p);
        }
        for (int i = l; i < r; ++i) {
            const auto p = std::make_pair(X[i], Y[i]);
            if (alEdges.find(p) != alEdges.end()) alEdges.erase(p);
        }
        alEdgesVec[l / B] = std::move(alEdges);
    }

    bool reved = false;

    auto solveL = [&]() {
        for (int i = 0; i < C; ++i) {
            if (X[i] > Y[i]) {
                std::swap(X[i], Y[i]);
            }
        }
        // reuse
        PPUnionFind uft(N);
        std::vector<std::vector<int>> graph(N);
        std::vector<char> isSeen(N);
        for (int l = 0; l < C; l += B) {
            const int r = std::min(l + B, C);
            // [l, r)

            // build Union Find
            std::vector<std::pair<int, int>> alVec;
            const auto &alEdges = alEdgesVec[l / B];
            for (const auto &[a, b] : alEdges) {
                if (reved) alVec.push_back({N - b - 1, N - a - 1});
                else alVec.push_back({a, b});
            }
            std::sort(alVec.begin(), alVec.end(), [&](const auto &x, const auto &y) {
                return x.second < y.second;
            });
            uft.reset();
            for (const auto &[a, b] : alVec) uft.merge(a, b, b);

            // answer queries
            for (int i = 0; i < Q; ++i) {
                if (not(l <= W[i] and W[i] < r)) continue;
                std::set<std::pair<int, int>> edges;
                for (int j = l; j <= W[i]; ++j) {
                    if (Y[j] > P[i]) continue;
                    const auto p = std::make_pair(X[j], Y[j]);
                    if (T[j] == 1) {
                        if (edges.find(p) != edges.end()) edges.erase(p);
                        continue;
                    }
                    if (edges.find(p) == edges.end()) edges.insert(p);
                }
                std::set<std::pair<int, int>> s2;
                for (int j = W[i] + 1; j < r; ++j) {
                    if (Y[j] > P[i]) continue;
                    const auto p = std::make_pair(X[j], Y[j]);
                    if (T[j] == 0) {
                        s2.insert(p);
                    } else {
                        if (s2.find(p) == s2.end()) {
                            edges.insert(p);
                        }
                    }
                }

                answer[i] += uft.countComp(P[i]) - (N - P[i] - 1);
                std::vector<int> vs;
                for (const auto &[a, b] : edges) {
                    const int x = uft.find(a, P[i]), y = uft.find(b, P[i]);
                    vs.push_back(x);
                    vs.push_back(y);
                    graph[x].push_back(y);
                    graph[y].push_back(x);
                }
                std::sort(vs.begin(), vs.end());
                vs.erase(std::unique(vs.begin(), vs.end()), vs.end());
                std::queue<int> que;
                auto st = [&](const int v) {
                    if (isSeen[v]) {
                        --answer[i];
                        return;
                    }
                    isSeen[v] = true;
                    que.push(v);
                    while (not que.empty()) {
                        const int f = que.front();
                        que.pop();
                        for (const int t : graph[f]) {
                            if (not isSeen[t]) {
                                isSeen[t] = true;
                                que.push(t);
                            }
                        }
                    }
                };
                for (const int v : vs) st(v);
                for (const int v : vs) {
                    while (not graph[v].empty()) graph[v].pop_back();
                    isSeen[v] = false;
                }
            }
        }
    };
    solveL();
    for (int i = 0; i < C; ++i) {
        X[i] = N - X[i] - 1;
        Y[i] = N - Y[i] - 1;
    }
    for (int i = 0; i < Q; ++i) {
        P[i] = N - P[i] - 2;
    }
    reved = true;
    solveL();
    return answer;
}

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35