oj.uz

Submission #681332

# Submission time Handle Problem Language Result Execution time Memory
681332 2023-01-12T18:38:13 Z nutella Collapse (JOI18_collapse) C++17
0 / 100
 15000 ms 7904 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>> 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) {
        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;
        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 = 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].stk.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].stk.size();

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

    return ans;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 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 10451 ms 5300 KB Output is correct
2 Incorrect 1047 ms 5296 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10568 ms 5260 KB Output is correct
2 Correct 10961 ms 5316 KB Output is correct
3 Correct 10946 ms 5308 KB Output is correct
4 Correct 10192 ms 5356 KB Output is correct
5 Correct 11359 ms 7144 KB Output is correct
6 Execution timed out 15092 ms 7904 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

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