oj.uz

Submission #686536

# Submission time Handle Problem Language Result Execution time Memory
686536 2023-01-25T12:07:54 Z wenqi Collapse (JOI18_collapse) C++17
100 / 100
 13787 ms 168168 KB 
#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;

int ans[100069];

struct UF {
    int parents[100069];
    int heights[100069];
    int ncomp;

    using Action = tuple<int, int, int, int>;
    vector<Action> actions;

    void init(int N) {
        for (int i = 0; i < N; i++) {
            parents[i] = i;
            heights[i] = 0;
        }
        ncomp = N;
    }

    int getp(int i) {
        return i == parents[i] ? i : getp(parents[i]);
    }

    bool merge(int i, int j) {
        int pi = getp(i);
        int pj = getp(j);
        if (pi == pj) return false;
        if (heights[pi] < heights[pj]) {
            swap(pi, pj);
        }
        actions.push_back({pj, parents[pj], pi, heights[pi]});
        parents[pj] = pi;
        heights[pi] = max(heights[pi], heights[pj] + 1);
        ncomp--;
        return true;
    }

    void pop() {
        auto [a, x, b, y] = actions.back();
        parents[a] = x;
        heights[b] = y;
        ncomp++;
        actions.pop_back();
    }
};

UF uf;

struct Point {
    int x, y;
};

struct Rect {
    int x1, x2, y1, y2;

    bool contains(const Rect &a) const {
        return x1 <= a.x1 and a.x2 <= x2 and y1 <= a.y1 and a.y2 <= y2;
    }

    bool outside(const Rect &a) const {
        return x2 < a.x1 or a.x2 < x1 or y2 < a.y1 or a.y2 < y1;
    }

    bool contains(const Point &a) const {
        return x1 <= a.x and a.x <= x2 and y1 <= a.y and a.y <= y2;
    }

    bool outside(const Point &a) const {
        return x2 < a.x or a.x < x1 or y2 < a.y or a.y < y1;
    }
};

using Update = tuple<Rect, int, int>;
using Query = pair<Point, int>;

void decomp(Rect cur, vector<Update> ups, vector<Query> queries) {
    if (queries.empty()) return;
    if (ups.empty()) {
        for (auto [p, qid] : queries) {
            ans[qid] = uf.ncomp;
        }
        return;
    }
    int cnt = 0;
    for (auto &[r, i, j] : ups) if (r.contains(cur)) cnt += uf.merge(i, j);
    if (cur.x1 == cur.x2 and cur.y1 == cur.y2) {
        for (auto [p, qid] : queries) {
            ans[qid] = uf.ncomp;
        }
        for (int i = 0; i < cnt; i++) uf.pop();
        return;
    }
    int mx = (cur.x1 + cur.x2) / 2;
    int my = (cur.y1 + cur.y2) / 2;
    Rect up {cur.x1, cur.x2, cur.y1, my}, down {cur.x1, cur.x2, my + 1, cur.y2}, left {cur.x1, mx, cur.y1, cur.y2}, right {mx + 1, cur.x2, cur.y1, cur.y2};
    vector<Update> uup, udown, uleft, uright;
    for (auto &[r, i, j] : ups) {
        if (r.contains(cur)) continue;
        if (not up.outside(r)) uup.push_back({r, i, j});
        if (not down.outside(r)) udown.push_back({r, i, j});
        if (not left.outside(r)) uleft.push_back({r, i, j});
        if (not right.outside(r)) uright.push_back({r, i, j});
    }
    if ((uup.size() + udown.size() < uleft.size() + uright.size() and cur.y1 != cur.y2) || cur.x1 == cur.x2) {
        vector<Query> qup, qdown;
        for (auto &[p, qid] : queries) {
            if (not up.outside(p)) qup.push_back({p, qid});
            if (not down.outside(p)) qdown.push_back({p, qid});
        }
        decomp(up, uup, qup);
        decomp(down, udown, qdown);
    } else {
        vector<Query> qleft, qright;
        for (auto &[p, qid] : queries) {
            if (not left.outside(p)) qleft.push_back({p, qid});
            if (not right.outside(p)) qright.push_back({p, qid});
        }
        decomp(left, uleft, qleft);
        decomp(right, uright, qright);
    }
    for (int i = 0; i < cnt; i++) uf.pop();
}

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
        ) {
    uf.init(N);
    vector<Query> queries;
    vector<Update> ups;
    for (int i = 0; i < W.size(); i++) {
        queries.push_back({{P[i], W[i]}, i});
    }
    map<pair<int, int>, int> S;
    for (int i = 0; i < T.size(); i++) {
        int x = min(X[i], Y[i]);
        int y = max(X[i], Y[i]);
        if (T[i]) {
            int y1 = S[{x, y}];
            ups.push_back({{0, x - 1, y1, i - 1}, x, y});
            ups.push_back({{y, N - 1, y1, i - 1}, x, y});
            S[{x, y}] = -1;
        } else {
            S[{x, y}] = i;
        }
    }
    int e = T.size() - 1;
    for (auto [a, b] : S) {
        if (b == -1) continue;
        auto [x, y] = a;
        int y1 = b;
        ups.push_back({{0, x - 1, y1, e}, x, y});
        ups.push_back({{y, N - 1, y1, e}, x, y});
    }
    decomp(Rect {0, N - 1, 0, (int) T.size() - 1}, ups, queries);
    for (int i = 0; i < W.size(); i++) {
        W[i] = ans[i];
    }
    return W;
}

Compilation message

collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:138:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     for (int i = 0; i < W.size(); i++) {
      |                     ~~^~~~~~~~~~
collapse.cpp:142:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for (int i = 0; i < T.size(); i++) {
      |                     ~~^~~~~~~~~~
collapse.cpp:163:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |     for (int i = 0; i < W.size(); i++) {
      |                     ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1220 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 18 ms 1880 KB Output is correct
6 Correct 95 ms 5716 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 6 ms 852 KB Output is correct
9 Correct 36 ms 2224 KB Output is correct
10 Correct 106 ms 3840 KB Output is correct
11 Correct 192 ms 6164 KB Output is correct
12 Correct 160 ms 8172 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 7096 KB Output is correct
2 Correct 30 ms 13528 KB Output is correct
3 Correct 179 ms 28972 KB Output is correct
4 Correct 34 ms 14480 KB Output is correct
5 Correct 255 ms 30788 KB Output is correct
6 Correct 66 ms 19496 KB Output is correct
7 Correct 288 ms 99888 KB Output is correct
8 Correct 355 ms 36280 KB Output is correct
9 Correct 32 ms 13244 KB Output is correct
10 Correct 39 ms 17732 KB Output is correct
11 Correct 54 ms 16564 KB Output is correct
12 Correct 408 ms 37224 KB Output is correct
13 Correct 440 ms 75892 KB Output is correct
14 Correct 406 ms 105588 KB Output is correct
15 Correct 361 ms 98856 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 6988 KB Output is correct
2 Correct 29 ms 10208 KB Output is correct
3 Correct 34 ms 9536 KB Output is correct
4 Correct 35 ms 9916 KB Output is correct
5 Correct 76 ms 9028 KB Output is correct
6 Correct 320 ms 13608 KB Output is correct
7 Correct 6422 ms 85704 KB Output is correct
8 Correct 11164 ms 110720 KB Output is correct
9 Correct 30 ms 10056 KB Output is correct
10 Correct 398 ms 11484 KB Output is correct
11 Correct 10218 ms 158536 KB Output is correct
12 Correct 13787 ms 118116 KB Output is correct
13 Correct 11380 ms 124872 KB Output is correct
14 Correct 13034 ms 118876 KB Output is correct
15 Correct 10607 ms 143256 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1220 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 852 KB Output is correct
5 Correct 18 ms 1880 KB Output is correct
6 Correct 95 ms 5716 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 6 ms 852 KB Output is correct
9 Correct 36 ms 2224 KB Output is correct
10 Correct 106 ms 3840 KB Output is correct
11 Correct 192 ms 6164 KB Output is correct
12 Correct 160 ms 8172 KB Output is correct
13 Correct 23 ms 7096 KB Output is correct
14 Correct 30 ms 13528 KB Output is correct
15 Correct 179 ms 28972 KB Output is correct
16 Correct 34 ms 14480 KB Output is correct
17 Correct 255 ms 30788 KB Output is correct
18 Correct 66 ms 19496 KB Output is correct
19 Correct 288 ms 99888 KB Output is correct
20 Correct 355 ms 36280 KB Output is correct
21 Correct 32 ms 13244 KB Output is correct
22 Correct 39 ms 17732 KB Output is correct
23 Correct 54 ms 16564 KB Output is correct
24 Correct 408 ms 37224 KB Output is correct
25 Correct 440 ms 75892 KB Output is correct
26 Correct 406 ms 105588 KB Output is correct
27 Correct 361 ms 98856 KB Output is correct
28 Correct 26 ms 6988 KB Output is correct
29 Correct 29 ms 10208 KB Output is correct
30 Correct 34 ms 9536 KB Output is correct
31 Correct 35 ms 9916 KB Output is correct
32 Correct 76 ms 9028 KB Output is correct
33 Correct 320 ms 13608 KB Output is correct
34 Correct 6422 ms 85704 KB Output is correct
35 Correct 11164 ms 110720 KB Output is correct
36 Correct 30 ms 10056 KB Output is correct
37 Correct 398 ms 11484 KB Output is correct
38 Correct 10218 ms 158536 KB Output is correct
39 Correct 13787 ms 118116 KB Output is correct
40 Correct 11380 ms 124872 KB Output is correct
41 Correct 13034 ms 118876 KB Output is correct
42 Correct 10607 ms 143256 KB Output is correct
43 Correct 1097 ms 34960 KB Output is correct
44 Correct 7620 ms 111580 KB Output is correct
45 Correct 1431 ms 36204 KB Output is correct
46 Correct 11218 ms 107184 KB Output is correct
47 Correct 28 ms 9840 KB Output is correct
48 Correct 43 ms 10160 KB Output is correct
49 Correct 416 ms 11336 KB Output is correct
50 Correct 2108 ms 21048 KB Output is correct
51 Correct 1545 ms 36844 KB Output is correct
52 Correct 6765 ms 62216 KB Output is correct
53 Correct 5851 ms 89740 KB Output is correct
54 Correct 9031 ms 81948 KB Output is correct
55 Correct 7400 ms 106760 KB Output is correct
56 Correct 8723 ms 110240 KB Output is correct
57 Correct 10078 ms 117544 KB Output is correct
58 Correct 11871 ms 107864 KB Output is correct
59 Correct 10552 ms 168168 KB Output is correct
60 Correct 12757 ms 117896 KB Output is correct