#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);
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();
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) {
data[j].unite(x, y);
}
for (int j = block2 + 1; j < siz; ++j) {
data[j].unite(x, y);
}
alive[fi] = 1, alive[se] = 2;
// cout << "added: " << x << " " << y << endl;
// cout << fi << ": 1\n" << se << ": 2\n";
} 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 = block * B;
for (int j = pos - 1; j >= lim; --j) {
if (alive[j] == 2) {
data[block].unite(e[a[j][2]][2], e[a[j][2]][3]);
}
}
lim = min(sza, lim + B);
for (int j = pos + 1; j < lim; ++j) {
if (alive[j] == 1) {
data[block].unite(e[a[j][2]][2], e[a[j][2]][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) {
| ~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
83 ms |
5692 KB |
Output is correct |
| 2 |
Incorrect |
60 ms |
5752 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
67 ms |
5668 KB |
Output is correct |
| 2 |
Correct |
81 ms |
5760 KB |
Output is correct |
| 3 |
Incorrect |
96 ms |
5728 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
