#include <bits/stdc++.h>
template <class T>
using Vec = std::vector<T>;
struct DSU {
Vec<int> par;
int cmp;
std::stack<std::tuple<int, int, int, int, int>> stack;
DSU(const int n): par(n, -1), cmp(n) { }
int find(int x) const {
while (par[x] >= 0) {
x = par[x];
}
return x;
}
int merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return 0;
}
if (par[x] > par[y]) {
std::swap(x, y);
}
stack.emplace(x, par[x], y, par[y], cmp);
par[x] += par[y];
par[y] = x;
cmp -= 1;
return 1;
}
void rollback() {
const auto [i, x, j, y, c] = stack.top();
stack.pop();
par[i] = x;
par[j] = y;
cmp = c;
}
};
struct Solver {
Vec<Vec<std::pair<int, int>>> edges;
Solver(const int t) {
int n = 1;
while (n < t) {
n <<= 1;
}
edges.resize(2 * n);
}
void add(int u, int v, int l, int r) {
l += size();
r += size();
while (l < r) {
if (l & 1) {
edges[l].emplace_back(u, v);
l += 1;
}
l >>= 1;
if (r & 1) {
r -= 1;
edges[r].emplace_back(u, v);
}
r >>= 1;
}
}
void dfs(int k, DSU &uf, Vec<int> &vec) {
int steps = 0;
for (const auto [u, v]: edges[k]) {
steps += uf.merge(u, v);
}
if (k >= size()) {
vec[k - size()] = uf.cmp;
}
else {
dfs(k * 2, uf, vec);
dfs(k * 2 + 1, uf, vec);
}
while (steps--) {
uf.rollback();
}
}
Vec<int> solve(int n, int t) {
DSU uf(n);
Vec<int> ret(size());
dfs(1, uf, ret);
ret.resize(t);
ret.shrink_to_fit();
return ret;
}
int size() const {
return edges.size() / 2;
}
};
Vec<int> simulateCollapse(int N, Vec<int> T, Vec<int> X, Vec<int> Y, Vec<int> W, Vec<int> P) {
const int C = T.size();
const int Q = W.size();
Vec<int> ret(Q);
if (std::count(P.begin(), P.end(), P.front()) == N) {
Solver sol(C);
std::map<std::pair<int, int>, int> state;
const int bad = P.front();
for (int i = 0; i < C; ++i) {
const auto p = std::minmax(X[i], Y[i]);
if (p.second <= bad || p.first > bad) {
if (state[p] == -1) {
state[p] = i;
}
else {
sol.add(p.first, p.second, state[p], i);
state[p] = -1;
}
}
}
for (const auto &[p, v]: state) {
if (v != -1) {
sol.add(p.first, p.second, v, C);
}
}
const auto vec = sol.solve(N, C);
for (int i = 0; i < Q; ++i) {
ret[i] = vec[W[i]];
}
}
return ret;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
620 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
28 ms |
2624 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
28 ms |
2540 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
620 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |