| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 686533 |
2023-01-25T12:06:11 Z |
wenqi |
Collapse (JOI18_collapse) |
C++17 |
|
24 ms |
7112 KB |
#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
int ans[100069];
struct UF {
int parents[100069];
int heights[100069];
int ncomp;
using Action = tuple<int, int, int, int>;
vector<Action> actions;
void init(int N) {
for (int i = 0; i < N; i++) {
parents[i] = i;
heights[i] = 0;
}
ncomp = N;
}
int getp(int i) {
return i == parents[i] ? i : getp(parents[i]);
}
bool merge(int i, int j) {
int pi = getp(i);
int pj = getp(j);
if (pi == pj) return false;
if (heights[pi] < heights[pj]) {
swap(pi, pj);
}
actions.push_back({pj, parents[pj], pi, heights[pi]});
parents[pj] = pi;
heights[pi] = max(heights[pi], heights[pj] + 1);
ncomp--;
return true;
}
void pop() {
auto [a, x, b, y] = actions.back();
parents[a] = x;
heights[b] = y;
ncomp++;
actions.pop_back();
}
};
UF uf;
struct Point {
int x, y;
};
struct Rect {
int x1, x2, y1, y2;
bool contains(const Rect &a) const {
return x1 <= a.x1 and a.x2 <= x2 and y1 <= a.y1 and a.y2 <= y2;
}
bool outside(const Rect &a) const {
return x2 < a.x1 or a.x2 < x1 or y2 < a.y1 or a.y2 < y1;
}
bool contains(const Point &a) const {
return x1 <= a.x and a.x <= x2 and y1 <= a.y and a.y <= y2;
}
bool outside(const Point &a) const {
return x2 < a.x or a.x < x1 or y2 < a.y or a.y < y1;
}
};
using Update = tuple<Rect, int, int>;
using Query = pair<Point, int>;
void decomp(Rect cur, vector<Update> ups, vector<Query> queries) {
if (queries.empty()) return;
if (ups.empty()) {
for (auto [p, qid] : queries) {
ans[qid] = uf.ncomp;
}
return;
}
int cnt = 0;
for (auto &[r, i, j] : ups) if (r.contains(cur)) cnt += uf.merge(i, j);
if (cur.x1 == cur.x2 and cur.y1 == cur.y2) {
for (auto [p, qid] : queries) {
ans[qid] = uf.ncomp;
}
for (int i = 0; i < cnt; i++) uf.pop();
return;
}
int mx = (cur.x1 + cur.x2) / 2;
int my = (cur.y1 + cur.y2) / 2;
Rect up {cur.x1, cur.x2, cur.y1, my}, down {cur.x1, cur.x2, my + 1, cur.y2}, left {cur.x1, mx, cur.y1, cur.y2}, right {mx + 1, cur.x2, cur.y1, cur.y2};
vector<Update> uup, udown, uleft, uright;
for (auto &[r, i, j] : ups) {
if (cur.contains(r)) continue;
if (not up.outside(r)) uup.push_back({r, i, j});
if (not down.outside(r)) udown.push_back({r, i, j});
if (not left.outside(r)) uleft.push_back({r, i, j});
if (not right.outside(r)) uright.push_back({r, i, j});
}
if ((uup.size() + udown.size() < uleft.size() + uright.size() and cur.y1 != cur.y2) || cur.x1 == cur.x2) {
vector<Query> qup, qdown;
for (auto &[p, qid] : queries) {
if (not up.outside(p)) qup.push_back({p, qid});
if (not down.outside(p)) qdown.push_back({p, qid});
}
decomp(up, uup, qup);
decomp(down, udown, qdown);
} else {
vector<Query> qleft, qright;
for (auto &[p, qid] : queries) {
if (not left.outside(p)) qleft.push_back({p, qid});
if (not right.outside(p)) qright.push_back({p, qid});
}
decomp(left, uleft, qleft);
decomp(right, uright, qright);
}
for (int i = 0; i < cnt; i++) uf.pop();
}
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
) {
uf.init(N);
vector<Query> queries;
vector<Update> ups;
for (int i = 0; i < W.size(); i++) {
queries.push_back({{P[i], W[i]}, i});
}
map<pair<int, int>, int> S;
for (int i = 0; i < T.size(); i++) {
int x = min(X[i], Y[i]);
int y = max(X[i], Y[i]);
if (T[i]) {
int y1 = S[{x, y}];
ups.push_back({{0, x - 1, y1, i - 1}, x, y});
ups.push_back({{y, N - 1, y1, i - 1}, x, y});
S[{x, y}] = -1;
} else {
S[{x, y}] = i;
}
}
int e = T.size() - 1;
for (auto [a, b] : S) {
if (b == -1) continue;
auto [x, y] = a;
int y1 = b;
ups.push_back({{0, x - 1, y1, e}, x, y});
ups.push_back({{y, N - 1, y1, e}, x, y});
}
decomp(Rect {0, N - 1, 0, (int) T.size() - 1}, ups, queries);
for (int i = 0; i < W.size(); i++) {
W[i] = ans[i];
}
return W;
}
Compilation message
collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:138:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for (int i = 0; i < W.size(); i++) {
| ~~^~~~~~~~~~
collapse.cpp:142:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for (int i = 0; i < T.size(); i++) {
| ~~^~~~~~~~~~
collapse.cpp:163:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | for (int i = 0; i < W.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
964 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
7108 KB |
Output is correct |
| 2 |
Incorrect |
24 ms |
6988 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
6984 KB |
Output is correct |
| 2 |
Incorrect |
23 ms |
7112 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
964 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
