oj.uz

Submission #711584

# Submission time Handle Problem Language Result Execution time Memory
711584 2023-03-17T09:19:16 Z Cyanmond Collapse (JOI18_collapse) C++17
5 / 100
 15000 ms 14364 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());
    }
};

constexpr int B = 300;

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] : 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) {
                    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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 468 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 13 ms 400 KB Output is correct
4 Correct 18 ms 340 KB Output is correct
5 Correct 85 ms 468 KB Output is correct
6 Correct 186 ms 788 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 6 ms 500 KB Output is correct
9 Correct 104 ms 848 KB Output is correct
10 Correct 179 ms 932 KB Output is correct
11 Correct 226 ms 1228 KB Output is correct
12 Correct 223 ms 1272 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2260 KB Output is correct
2 Correct 49 ms 2260 KB Output is correct
3 Correct 5105 ms 4616 KB Output is correct
4 Correct 248 ms 2644 KB Output is correct
5 Correct 7124 ms 6352 KB Output is correct
6 Correct 1809 ms 3556 KB Output is correct
7 Execution timed out 15079 ms 13276 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2244 KB Output is correct
2 Correct 64 ms 2244 KB Output is correct
3 Correct 162 ms 2252 KB Output is correct
4 Correct 363 ms 2252 KB Output is correct
5 Correct 3121 ms 2428 KB Output is correct
6 Correct 3248 ms 3692 KB Output is correct
7 Correct 11821 ms 11248 KB Output is correct
8 Execution timed out 15019 ms 14364 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 468 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 13 ms 400 KB Output is correct
4 Correct 18 ms 340 KB Output is correct
5 Correct 85 ms 468 KB Output is correct
6 Correct 186 ms 788 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 6 ms 500 KB Output is correct
9 Correct 104 ms 848 KB Output is correct
10 Correct 179 ms 932 KB Output is correct
11 Correct 226 ms 1228 KB Output is correct
12 Correct 223 ms 1272 KB Output is correct
13 Correct 29 ms 2260 KB Output is correct
14 Correct 49 ms 2260 KB Output is correct
15 Correct 5105 ms 4616 KB Output is correct
16 Correct 248 ms 2644 KB Output is correct
17 Correct 7124 ms 6352 KB Output is correct
18 Correct 1809 ms 3556 KB Output is correct
19 Execution timed out 15079 ms 13276 KB Time limit exceeded
20 Halted 0 ms 0 KB -