oj.uz

Submission #681330

# Submission time Handle Problem Language Result Execution time Memory
681330 2023-01-12T18:35:56 Z nutella Collapse (JOI18_collapse) C++17
0 / 100
 10236 ms 5352 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();
        }
    }
};

void my_assert(bool f) {
    while (!f) {
        cout << "here" << endl;
    }
}

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 = 100;

    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);
    for (auto [tx, type, i] : events) {
        if (type == -1) {
            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();

            int block1 = fi / B, block2 = se / B;
            for (int j = 0; j < block1; ++j) {
                data[j].unite(x, y);
            }
            for (int j = block2 + 1; j < siz; ++j) {
                data[j].unite(x, y);
            }

            alive[fi] = 1, alive[se] = 1;
        } else {
            int pos = lower_bound(a.begin(), a.end(), array{P[i], 0, i}) - a.begin();
            int block = pos / B;

            int save = data[block].rb.size();

            int lim = 0 /*block * B*/;
            int limr = min(sza, numeric_limits<int>::max() /*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 Incorrect 4 ms 964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10236 ms 5352 KB Output is correct
2 Incorrect 1049 ms 5336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10025 ms 5320 KB Output is correct
2 Correct 9938 ms 5324 KB Output is correct
3 Incorrect 10231 ms 5320 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 964 KB Output isn't correct
2 Halted 0 ms 0 KB -