oj.uz

답안 #711579

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
711579 2023-03-17T09:04:32 Z Cyanmond Collapse (JOI18_collapse) C++17
0 / 100
 15000 ms 4688 KB 
#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 - (itr - compS.begin());
    }
};

constexpr int B = 3;

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();
    std::vector<int> answer(Q);

    auto solveL = [&]() {
        for (int i = 0; i < C; ++i) {
            if (X[i] > Y[i]) {
                std::swap(X[i], Y[i]);
            }
        }
        // reuse
        std::vector<std::vector<int>> graph(N);
        std::vector<bool> isSeen(N);
        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);
            }
            std::vector<std::pair<int, int>> alVec;
            for (const auto &[a, b] : alEdges) alVec.push_back({a, b});
            std::sort(alVec.begin(), alVec.end(), [&](const auto &x, const auto &y) {
                return x.second < y.second;
            });

            PPUnionFind uft(N);
            for (const auto &[a, b] : alEdges) 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);
                    else edges.erase(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];
                    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) {
                    graph[v].clear();
                    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;
    }
    solveL();
    return answer;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 504 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Incorrect 4 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 2260 KB Output is correct
2 Correct 43 ms 2260 KB Output is correct
3 Execution timed out 15084 ms 4688 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 2260 KB Output is correct
2 Incorrect 50 ms 2260 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 504 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Incorrect 4 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -