#include "collapse.h"
#include <bits/stdc++.h>
constexpr int inf = 1 << 30;
struct PPUnionFind {
int n;
std::vector<int> data, time;
std::vector<int> compS;
PPUnionFind(int n_) : n(n_) {
data.assign(n, -1);
time.assign(n, inf);
}
int find(int v, int t) {
if (time[v] > t) return v;
return find(data[v], t);
}
void merge(int a, int b, int t) {
a = find(a, t);
b = find(b, t);
if (a == b) return;
if (data[a] > data[b]) std::swap(a, b);
data[a] += data[b];
data[b] = a;
time[b] = t;
compS.push_back(t);
}
int countComp(int t) {
auto itr = std::upper_bound(compS.begin(), compS.end(), t);
return n - (int)(itr - compS.begin());
}
void reset() {
compS.clear();
data.assign(n, -1);
time.assign(n, inf);
}
};
constexpr int B = 500;
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 C = (int)T.size(), Q = (int)P.size();
for (int i = 0; i < C; ++i) {
if (X[i] > Y[i]) {
std::swap(X[i], Y[i]);
}
}
std::vector<int> answer(Q);
const int blocks = (C + B - 1) / B;
std::vector<std::set<std::pair<int, int>>> alEdgesVec(blocks);
for (int l = 0; l < C; l += B) {
const int r = std::min(l + B, C);
// [l, r)
// build Union Find
std::set<std::pair<int, int>> alEdges;
for (int i = 0; i < l; ++i) {
const auto p = std::make_pair(X[i], Y[i]);
if (alEdges.find(p) == alEdges.end()) alEdges.insert(p);
else alEdges.erase(p);
}
for (int i = l; i < r; ++i) {
const auto p = std::make_pair(X[i], Y[i]);
if (alEdges.find(p) != alEdges.end()) alEdges.erase(p);
}
alEdgesVec[l / B] = std::move(alEdges);
}
bool reved = false;
auto solveL = [&]() {
for (int i = 0; i < C; ++i) {
if (X[i] > Y[i]) {
std::swap(X[i], Y[i]);
}
}
// reuse
PPUnionFind uft(N);
std::vector<std::vector<int>> graph(N);
std::vector<char> isSeen(N);
for (int l = 0; l < C; l += B) {
const int r = std::min(l + B, C);
// [l, r)
// build Union Find
std::vector<std::pair<int, int>> alVec;
const auto &alEdges = alEdgesVec[l / B];
for (const auto &[a, b] : alEdges) {
if (reved) alVec.push_back({N - b - 1, N - a - 1});
else alVec.push_back({a, b});
}
std::sort(alVec.begin(), alVec.end(), [&](const auto &x, const auto &y) {
return x.second < y.second;
});
for (const auto &[a, b] : alVec) uft.merge(a, b, b);
// answer queries
uft.reset();
for (int i = 0; i < Q; ++i) {
if (not(l <= W[i] and W[i] < r)) continue;
std::set<std::pair<int, int>> edges;
for (int j = l; j <= W[i]; ++j) {
if (Y[j] > P[i]) continue;
const auto p = std::make_pair(X[j], Y[j]);
if (T[j] == 1) {
if (edges.find(p) != edges.end()) edges.erase(p);
continue;
}
if (edges.find(p) == edges.end()) edges.insert(p);
}
std::set<std::pair<int, int>> s2;
for (int j = W[i] + 1; j < r; ++j) {
if (Y[j] > P[i]) continue;
const auto p = std::make_pair(X[j], Y[j]);
if (T[j] == 0) {
s2.insert(p);
} else {
if (s2.find(p) == s2.end()) {
edges.insert(p);
}
}
}
answer[i] += uft.countComp(P[i]) - (N - P[i] - 1);
std::vector<int> vs;
for (const auto &[a, b] : edges) {
const int x = uft.find(a, P[i]), y = uft.find(b, P[i]);
vs.push_back(x);
vs.push_back(y);
graph[x].push_back(y);
graph[y].push_back(x);
}
std::sort(vs.begin(), vs.end());
vs.erase(std::unique(vs.begin(), vs.end()), vs.end());
std::queue<int> que;
auto st = [&](const int v) {
if (isSeen[v]) {
--answer[i];
return;
}
isSeen[v] = true;
que.push(v);
while (not que.empty()) {
const int f = que.front();
que.pop();
for (const int t : graph[f]) {
if (not isSeen[t]) {
isSeen[t] = true;
que.push(t);
}
}
}
};
for (const int v : vs) st(v);
for (const int v : vs) {
while (not graph[v].empty()) graph[v].pop_back();
isSeen[v] = false;
}
}
}
};
solveL();
for (int i = 0; i < C; ++i) {
X[i] = N - X[i] - 1;
Y[i] = N - Y[i] - 1;
}
for (int i = 0; i < Q; ++i) {
P[i] = N - P[i] - 2;
}
reved = true;
solveL();
return answer;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
468 KB |
Output is correct |
| 2 |
Correct |
4 ms |
352 KB |
Output is correct |
| 3 |
Correct |
14 ms |
424 KB |
Output is correct |
| 4 |
Correct |
21 ms |
420 KB |
Output is correct |
| 5 |
Correct |
144 ms |
576 KB |
Output is correct |
| 6 |
Incorrect |
473 ms |
1740 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
2380 KB |
Output is correct |
| 2 |
Correct |
48 ms |
2380 KB |
Output is correct |
| 3 |
Incorrect |
3379 ms |
4744 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
2252 KB |
Output is correct |
| 2 |
Correct |
72 ms |
2248 KB |
Output is correct |
| 3 |
Correct |
317 ms |
2132 KB |
Output is correct |
| 4 |
Correct |
439 ms |
2280 KB |
Output is correct |
| 5 |
Correct |
8373 ms |
2308 KB |
Output is correct |
| 6 |
Incorrect |
7496 ms |
3912 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
468 KB |
Output is correct |
| 2 |
Correct |
4 ms |
352 KB |
Output is correct |
| 3 |
Correct |
14 ms |
424 KB |
Output is correct |
| 4 |
Correct |
21 ms |
420 KB |
Output is correct |
| 5 |
Correct |
144 ms |
576 KB |
Output is correct |
| 6 |
Incorrect |
473 ms |
1740 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
