#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, b);
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 - (itr - compS.begin());
}
};
constexpr int B = 3;
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();
std::vector<int> answer(Q);
auto solveL = [&]() {
for (int i = 0; i < C; ++i) {
if (X[i] > Y[i]) {
std::swap(X[i], Y[i]);
}
}
int blocks = (C + B - 1) / B;
// reuse
std::vector<std::vector<int>> graph(N);
std::vector<bool> isSeen(N);
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);
}
std::vector<std::pair<int, int>> alVec;
for (const auto &[a, b] : alEdges) alVec.push_back({a, b});
std::sort(alVec.begin(), alVec.end(), [&](const auto &x, const auto &y) {
return x.second < y.second;
});
PPUnionFind uft(N);
for (const auto &[a, b] : alEdges) uft.merge(a, b, b);
// answer queries
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);
else edges.erase(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];
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) {
graph[v].clear();
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;
}
solveL();
return answer;
}
Compilation message
collapse.cpp: In lambda function:
collapse.cpp:51:13: warning: unused variable 'blocks' [-Wunused-variable]
51 | int blocks = (C + B - 1) / B;
| ^~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
221 ms |
560 KB |
Output is correct |
| 2 |
Correct |
3 ms |
468 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
420 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
33 ms |
2616 KB |
Output is correct |
| 2 |
Correct |
47 ms |
2644 KB |
Output is correct |
| 3 |
Execution timed out |
15020 ms |
5960 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
30 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
51 ms |
2644 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
221 ms |
560 KB |
Output is correct |
| 2 |
Correct |
3 ms |
468 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
420 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
