oj.uz

Submission #711596

# Submission time Handle Problem Language Result Execution time Memory
711596 2023-03-17T09:33:29 Z Cyanmond Collapse (JOI18_collapse) C++17
35 / 100
 15000 ms 482520 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 = 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
        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;
            });

            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) {
                    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 468 KB Output is correct
2 Correct 3 ms 396 KB Output is correct
3 Correct 13 ms 396 KB Output is correct
4 Correct 20 ms 396 KB Output is correct
5 Correct 125 ms 508 KB Output is correct
6 Correct 320 ms 1732 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Correct 167 ms 752 KB Output is correct
10 Correct 299 ms 936 KB Output is correct
11 Correct 385 ms 1924 KB Output is correct
12 Correct 365 ms 1960 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2252 KB Output is correct
2 Correct 50 ms 2220 KB Output is correct
3 Correct 2800 ms 4620 KB Output is correct
4 Correct 260 ms 2260 KB Output is correct
5 Correct 4536 ms 5060 KB Output is correct
6 Correct 3604 ms 3636 KB Output is correct
7 Correct 9767 ms 474176 KB Output is correct
8 Correct 4332 ms 5844 KB Output is correct
9 Correct 47 ms 5576 KB Output is correct
10 Correct 102 ms 5620 KB Output is correct
11 Correct 3438 ms 6140 KB Output is correct
12 Correct 5281 ms 9552 KB Output is correct
13 Correct 8377 ms 195208 KB Output is correct
14 Correct 11350 ms 478760 KB Output is correct
15 Correct 10269 ms 478584 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2252 KB Output is correct
2 Correct 68 ms 2368 KB Output is correct
3 Correct 165 ms 2364 KB Output is correct
4 Correct 394 ms 2372 KB Output is correct
5 Correct 6900 ms 2436 KB Output is correct
6 Correct 6649 ms 3736 KB Output is correct
7 Correct 11006 ms 268348 KB Output is correct
8 Correct 13730 ms 474664 KB Output is correct
9 Correct 56 ms 6256 KB Output is correct
10 Correct 7002 ms 6692 KB Output is correct
11 Correct 13701 ms 482432 KB Output is correct
12 Correct 14460 ms 482216 KB Output is correct
13 Correct 14782 ms 482156 KB Output is correct
14 Execution timed out 15092 ms 482520 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 468 KB Output is correct
2 Correct 3 ms 396 KB Output is correct
3 Correct 13 ms 396 KB Output is correct
4 Correct 20 ms 396 KB Output is correct
5 Correct 125 ms 508 KB Output is correct
6 Correct 320 ms 1732 KB Output is correct
7 Correct 3 ms 468 KB Output is correct
8 Correct 6 ms 468 KB Output is correct
9 Correct 167 ms 752 KB Output is correct
10 Correct 299 ms 936 KB Output is correct
11 Correct 385 ms 1924 KB Output is correct
12 Correct 365 ms 1960 KB Output is correct
13 Correct 31 ms 2252 KB Output is correct
14 Correct 50 ms 2220 KB Output is correct
15 Correct 2800 ms 4620 KB Output is correct
16 Correct 260 ms 2260 KB Output is correct
17 Correct 4536 ms 5060 KB Output is correct
18 Correct 3604 ms 3636 KB Output is correct
19 Correct 9767 ms 474176 KB Output is correct
20 Correct 4332 ms 5844 KB Output is correct
21 Correct 47 ms 5576 KB Output is correct
22 Correct 102 ms 5620 KB Output is correct
23 Correct 3438 ms 6140 KB Output is correct
24 Correct 5281 ms 9552 KB Output is correct
25 Correct 8377 ms 195208 KB Output is correct
26 Correct 11350 ms 478760 KB Output is correct
27 Correct 10269 ms 478584 KB Output is correct
28 Correct 31 ms 2252 KB Output is correct
29 Correct 68 ms 2368 KB Output is correct
30 Correct 165 ms 2364 KB Output is correct
31 Correct 394 ms 2372 KB Output is correct
32 Correct 6900 ms 2436 KB Output is correct
33 Correct 6649 ms 3736 KB Output is correct
34 Correct 11006 ms 268348 KB Output is correct
35 Correct 13730 ms 474664 KB Output is correct
36 Correct 56 ms 6256 KB Output is correct
37 Correct 7002 ms 6692 KB Output is correct
38 Correct 13701 ms 482432 KB Output is correct
39 Correct 14460 ms 482216 KB Output is correct
40 Correct 14782 ms 482156 KB Output is correct
41 Execution timed out 15092 ms 482520 KB Time limit exceeded
42 Halted 0 ms 0 KB -