oj.uz

답안 #711589

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
711589 2023-03-17T09:25:53 Z Cyanmond Collapse (JOI18_collapse) C++17
35 / 100
 15000 ms 15952 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 = 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();
    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<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::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) {
                    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;
    }
    solveL();
    return answer;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 468 KB Output is correct
2 Correct 4 ms 400 KB Output is correct
3 Correct 12 ms 396 KB Output is correct
4 Correct 19 ms 388 KB Output is correct
5 Correct 156 ms 468 KB Output is correct
6 Correct 377 ms 848 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 7 ms 468 KB Output is correct
9 Correct 219 ms 756 KB Output is correct
10 Correct 355 ms 924 KB Output is correct
11 Correct 434 ms 1128 KB Output is correct
12 Correct 448 ms 1120 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 2260 KB Output is correct
2 Correct 53 ms 2252 KB Output is correct
3 Correct 3836 ms 4612 KB Output is correct
4 Correct 257 ms 2260 KB Output is correct
5 Correct 6190 ms 4688 KB Output is correct
6 Correct 4834 ms 2740 KB Output is correct
7 Correct 12924 ms 11384 KB Output is correct
8 Correct 5835 ms 5216 KB Output is correct
9 Correct 46 ms 5460 KB Output is correct
10 Correct 100 ms 5500 KB Output is correct
11 Correct 4280 ms 5928 KB Output is correct
12 Correct 6930 ms 9656 KB Output is correct
13 Correct 11374 ms 11832 KB Output is correct
14 Correct 14246 ms 15496 KB Output is correct
15 Correct 13249 ms 15952 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 2284 KB Output is correct
2 Correct 64 ms 2252 KB Output is correct
3 Correct 172 ms 2256 KB Output is correct
4 Correct 389 ms 2360 KB Output is correct
5 Correct 7274 ms 2308 KB Output is correct
6 Correct 7853 ms 2724 KB Output is correct
7 Correct 11662 ms 9388 KB Output is correct
8 Execution timed out 15086 ms 12036 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 468 KB Output is correct
2 Correct 4 ms 400 KB Output is correct
3 Correct 12 ms 396 KB Output is correct
4 Correct 19 ms 388 KB Output is correct
5 Correct 156 ms 468 KB Output is correct
6 Correct 377 ms 848 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 7 ms 468 KB Output is correct
9 Correct 219 ms 756 KB Output is correct
10 Correct 355 ms 924 KB Output is correct
11 Correct 434 ms 1128 KB Output is correct
12 Correct 448 ms 1120 KB Output is correct
13 Correct 34 ms 2260 KB Output is correct
14 Correct 53 ms 2252 KB Output is correct
15 Correct 3836 ms 4612 KB Output is correct
16 Correct 257 ms 2260 KB Output is correct
17 Correct 6190 ms 4688 KB Output is correct
18 Correct 4834 ms 2740 KB Output is correct
19 Correct 12924 ms 11384 KB Output is correct
20 Correct 5835 ms 5216 KB Output is correct
21 Correct 46 ms 5460 KB Output is correct
22 Correct 100 ms 5500 KB Output is correct
23 Correct 4280 ms 5928 KB Output is correct
24 Correct 6930 ms 9656 KB Output is correct
25 Correct 11374 ms 11832 KB Output is correct
26 Correct 14246 ms 15496 KB Output is correct
27 Correct 13249 ms 15952 KB Output is correct
28 Correct 34 ms 2284 KB Output is correct
29 Correct 64 ms 2252 KB Output is correct
30 Correct 172 ms 2256 KB Output is correct
31 Correct 389 ms 2360 KB Output is correct
32 Correct 7274 ms 2308 KB Output is correct
33 Correct 7853 ms 2724 KB Output is correct
34 Correct 11662 ms 9388 KB Output is correct
35 Execution timed out 15086 ms 12036 KB Time limit exceeded
36 Halted 0 ms 0 KB -