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