oj.uz

Submission #681344

# Submission time Handle Problem Language Result Execution time Memory
681344 2023-01-12T18:47:28 Z nutella Collapse (JOI18_collapse) C++17
30 / 100
 10268 ms 494420 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{}, S = 0;

    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;
        }
        S += 1;
        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();
        S -= 1;
        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 = 500;

    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].S;

            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{}, S = 0;
      |         ^
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:54: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]
   54 |         while (stk.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 94 ms 5440 KB Output is correct
2 Incorrect 63 ms 5272 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 5380 KB Output is correct
2 Correct 111 ms 5280 KB Output is correct
3 Correct 117 ms 5368 KB Output is correct
4 Correct 134 ms 5544 KB Output is correct
5 Correct 148 ms 5568 KB Output is correct
6 Correct 164 ms 6092 KB Output is correct
7 Correct 890 ms 20988 KB Output is correct
8 Correct 3834 ms 68260 KB Output is correct
9 Correct 177 ms 162504 KB Output is correct
10 Correct 240 ms 165088 KB Output is correct
11 Correct 5951 ms 493812 KB Output is correct
12 Correct 10268 ms 494420 KB Output is correct
13 Correct 6757 ms 494036 KB Output is correct
14 Correct 10263 ms 494288 KB Output is correct
15 Correct 6015 ms 493864 KB Output is correct

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 -