oj.uz

Submission #711599

# Submission time Handle Problem Language Result Execution time Memory
711599 2023-03-17T09:35:57 Z Cyanmond Collapse (JOI18_collapse) C++17
100 / 100
 14772 ms 483260 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 - (int)(itr - compS.begin());
    }

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

constexpr int B = 500;

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 572 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 12 ms 340 KB Output is correct
4 Correct 22 ms 340 KB Output is correct
5 Correct 144 ms 556 KB Output is correct
6 Correct 318 ms 1816 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 7 ms 596 KB Output is correct
9 Correct 164 ms 856 KB Output is correct
10 Correct 313 ms 1044 KB Output is correct
11 Correct 405 ms 2108 KB Output is correct
12 Correct 377 ms 2248 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2632 KB Output is correct
2 Correct 50 ms 2628 KB Output is correct
3 Correct 3014 ms 5004 KB Output is correct
4 Correct 269 ms 2644 KB Output is correct
5 Correct 4805 ms 5424 KB Output is correct
6 Correct 4025 ms 4184 KB Output is correct
7 Correct 10264 ms 474536 KB Output is correct
8 Correct 4418 ms 6372 KB Output is correct
9 Correct 47 ms 6024 KB Output is correct
10 Correct 100 ms 6008 KB Output is correct
11 Correct 3368 ms 6088 KB Output is correct
12 Correct 5051 ms 10068 KB Output is correct
13 Correct 8282 ms 195528 KB Output is correct
14 Correct 11007 ms 479172 KB Output is correct
15 Correct 10006 ms 479356 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2644 KB Output is correct
2 Correct 64 ms 2644 KB Output is correct
3 Correct 158 ms 2692 KB Output is correct
4 Correct 385 ms 2736 KB Output is correct
5 Correct 6783 ms 2772 KB Output is correct
6 Correct 5881 ms 4056 KB Output is correct
7 Correct 8944 ms 269028 KB Output is correct
8 Correct 13355 ms 475168 KB Output is correct
9 Correct 51 ms 6276 KB Output is correct
10 Correct 7069 ms 6584 KB Output is correct
11 Correct 14271 ms 483020 KB Output is correct
12 Correct 14585 ms 482956 KB Output is correct
13 Correct 14373 ms 482560 KB Output is correct
14 Correct 14505 ms 480352 KB Output is correct
15 Correct 13649 ms 482396 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 572 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 12 ms 340 KB Output is correct
4 Correct 22 ms 340 KB Output is correct
5 Correct 144 ms 556 KB Output is correct
6 Correct 318 ms 1816 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 7 ms 596 KB Output is correct
9 Correct 164 ms 856 KB Output is correct
10 Correct 313 ms 1044 KB Output is correct
11 Correct 405 ms 2108 KB Output is correct
12 Correct 377 ms 2248 KB Output is correct
13 Correct 30 ms 2632 KB Output is correct
14 Correct 50 ms 2628 KB Output is correct
15 Correct 3014 ms 5004 KB Output is correct
16 Correct 269 ms 2644 KB Output is correct
17 Correct 4805 ms 5424 KB Output is correct
18 Correct 4025 ms 4184 KB Output is correct
19 Correct 10264 ms 474536 KB Output is correct
20 Correct 4418 ms 6372 KB Output is correct
21 Correct 47 ms 6024 KB Output is correct
22 Correct 100 ms 6008 KB Output is correct
23 Correct 3368 ms 6088 KB Output is correct
24 Correct 5051 ms 10068 KB Output is correct
25 Correct 8282 ms 195528 KB Output is correct
26 Correct 11007 ms 479172 KB Output is correct
27 Correct 10006 ms 479356 KB Output is correct
28 Correct 29 ms 2644 KB Output is correct
29 Correct 64 ms 2644 KB Output is correct
30 Correct 158 ms 2692 KB Output is correct
31 Correct 385 ms 2736 KB Output is correct
32 Correct 6783 ms 2772 KB Output is correct
33 Correct 5881 ms 4056 KB Output is correct
34 Correct 8944 ms 269028 KB Output is correct
35 Correct 13355 ms 475168 KB Output is correct
36 Correct 51 ms 6276 KB Output is correct
37 Correct 7069 ms 6584 KB Output is correct
38 Correct 14271 ms 483020 KB Output is correct
39 Correct 14585 ms 482956 KB Output is correct
40 Correct 14373 ms 482560 KB Output is correct
41 Correct 14505 ms 480352 KB Output is correct
42 Correct 13649 ms 482396 KB Output is correct
43 Correct 5750 ms 6696 KB Output is correct
44 Correct 13937 ms 475764 KB Output is correct
45 Correct 7118 ms 7788 KB Output is correct
46 Correct 13475 ms 476792 KB Output is correct
47 Correct 50 ms 6216 KB Output is correct
48 Correct 115 ms 6284 KB Output is correct
49 Correct 6099 ms 6632 KB Output is correct
50 Correct 7544 ms 11804 KB Output is correct
51 Correct 7340 ms 12176 KB Output is correct
52 Correct 10594 ms 104596 KB Output is correct
53 Correct 11072 ms 104992 KB Output is correct
54 Correct 13107 ms 199772 KB Output is correct
55 Correct 11944 ms 197888 KB Output is correct
56 Correct 13749 ms 293260 KB Output is correct
57 Correct 13540 ms 388984 KB Output is correct
58 Correct 13683 ms 389364 KB Output is correct
59 Correct 14772 ms 483260 KB Output is correct
60 Correct 14419 ms 482932 KB Output is correct