oj.uz

Submission #681320

# Submission time Handle Problem Language Result Execution time Memory
681320 2023-01-12T18:22:36 Z nutella Collapse (JOI18_collapse) C++17
0 / 100
 90 ms 10244 KB 
#include <bits/stdc++.h>
#include "collapse.h"

using namespace std;
using ll = long long;

constexpr int inf = 1e9 + 7;

struct DSU {
    vector<int> p, sz;
    vector<pair<int, int>> rb;

    DSU(int n) : p(n), sz(n, 1) {
        iota(p.begin(), p.end(), 0);
    }

    DSU() = default;

    int get(int x) {
        return p[x] == x ? x : p[x] = get(p[x]);
    }

    bool unite(int a, int b) {
        a = get(a), b = get(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        rb.emplace_back(a, b);
        sz[a] += sz[b];
        return true;
    }

    void undo() {
        auto [a, b] = rb.back();
        p[b] = b;
        sz[a] -= sz[b];
        rb.pop_back();
    }

    void rollback(int siz) {
        while (rb.size() > siz) {
            undo();
        }
    }
};

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 q = P.size(), c = T.size();


    map<pair<int, int>, int> last;

    vector<array<int, 4>> e;

    for (int i = 0; i < c; ++i) {
        if (X[i] > Y[i]) {
            swap(X[i], Y[i]);
        }
        if (T[i] == 0) {
            last[{X[i], Y[i]}] = i;
        } else {
            e.push_back({last[{X[i], Y[i]}], i, X[i], Y[i]});
            last.erase({X[i], Y[i]});
        }
    }

    for (auto [x, y] : last) {
        e.push_back({y, c, x.first, x.second});
    }

    const int sze = e.size();

    vector<array<int, 3>> events;
    for (int i = 0; i < sze; ++i) {
        events.push_back({e[i][0], 0, i});
        events.push_back({e[i][1], -1, i});
    }

    for (int i = 0; i < q; ++i) {
        events.push_back({W[i], 1, i});
    }

    sort(events.begin(), events.end());


    vector<array<int, 3>> a;
    for (int i = 0; i < sze; ++i) {
        a.push_back({e[i][2], -1, i});
        a.push_back({e[i][3], -2, i});
    }
    for (int i = 0; i < q; ++i) {
        a.push_back({P[i], 0, i});
    }
    sort(a.begin(), a.end());

    constexpr int B = 320;

    const int siz = (a.size() + B - 1) / B, sza = a.size();

    vector<DSU> data(siz);
    for (int i = 0; i < siz; ++i) {
        data[i] = DSU(n);
    }
    vector<int> alive(sza);

    vector<int> ans(q);
    int cntt = 0;
    for (auto [tx, type, i] : events) {
        if (type == -1) {
            assert(cntt == q);
            break;
        } else if (type == 0) {
            int x = e[i][2], y = e[i][3];
            int fi = lower_bound(a.begin(), a.end(), array{x, -1, i}) - a.begin();
            int se = lower_bound(a.begin(), a.end(), array{y, -2, i}) - a.begin();
            auto aa = array{x, -1, i};
            assert(a[fi] == aa);
            aa = array{y, -2, i};
            assert(a[se] == aa);
            int block1 = fi / B, block2 = se / B;
            for (int j = 0; j < block1; ++j) {
//                if (j == 8) {
//                    cout << x << " " << y << endl;
//                }
                data[j].unite(x, y);
            }
            for (int j = block2 + 1; j < siz; ++j) {

//                if (j == 8) {
//                    cout << x << " " << y << endl;
//                }
                data[j].unite(x, y);
            }
            alive[fi] = 1, alive[se] = 2;
//            cout << "added: " << x << " " << y << endl;
//            cout << fi << ": 1\n" << se << ": 2\n";
        } else {
            cntt += 1;
            int pos = lower_bound(a.begin(), a.end(), array{P[i], 0, i}) - a.begin();
//            cout << pos << endl;
            int block = pos / B;
            int save = data[block].rb.size();
            int lim = block * B;
            int limr = min(sza, lim + B);
            for (int j = lim; j < limr; ++j) {
                if (alive[j]) {
                    int jj = a[j][2];
                    if (e[jj][2] > P[i] || e[jj][3] <= P[i]) {
                        data[block].unite(e[jj][2], e[jj][3]);
                    }
                }
            }
            ans[i] = n - data[block].rb.size();
            data[block].rollback(save);
        }
    }

    return ans;
}

Compilation message

collapse.cpp: In member function 'void DSU::rollback(int)':
collapse.cpp:41:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |         while (rb.size() > siz) {
      |                ~~~~~~~~~~^~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 1844 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 5744 KB Output is correct
2 Runtime error 60 ms 10244 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 5624 KB Output is correct
2 Correct 90 ms 5576 KB Output is correct
3 Incorrect 88 ms 5600 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 1844 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -