Submission #681341

#	Time	Username	Problem	Language	Result	Execution time	Memory
681341		nutella	Collapse (JOI18_collapse)	C++17	0 / 100	82 ms	5320 KiB

collapse

#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>> stk;
    int n{};

    DSU() = default;

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

    int leader(int a) {
        return p[a] == a ? a : leader(p[a]);
    }

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

    bool same(int a, int b) {
        return leader(a) == leader(b);
    }

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

    void rollback(int siz) {
        while (stk.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 = 200;

    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].stk.size();
            assert(save == 0);

            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], true);
                    }
                }
            }

            ans[i] = n - data[block].stk.size();

            data[block].rollback(save);
        }
    }

    return ans;
}

Compilation message (stderr)

collapse.cpp: In constructor 'DSU::DSU(int)':
collapse.cpp:12:9: warning: 'DSU::n' will be initialized after [-Wreorder]
   12 |     int n{};
      |         ^
collapse.cpp:10:17: warning:   'std::vector<int> DSU::p' [-Wreorder]
   10 |     vector<int> p, sz;
      |                 ^
collapse.cpp:16:5: warning:   when initialized here [-Wreorder]
   16 |     DSU(int n) : n(n), p(n), sz(n, 1) {
      |     ^~~
collapse.cpp: In member function 'void DSU::rollback(int)':
collapse.cpp:52:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |         while (stk.size() > siz) {
      |                ~~~~~~~~~~~^~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 35