#include "parks.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
using namespace std;
using i32 = int;
//#define int long long
#define len(x) (int)(x.size())
template<typename T>
using vec = vector<T>;
struct DSU {
public:
DSU() : _n(0) {}
explicit DSU(int n) : _n(n), parent_or_size(n, -1) {}
int unite(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
int x = leader(a), y = leader(b);
if (x == y) return x;
if (-parent_or_size[x] < -parent_or_size[y]) std::swap(x, y);
parent_or_size[x] += parent_or_size[y];
parent_or_size[y] = x;
return x;
}
bool one(int a, int b) {
assert(0 <= a && a < _n);
assert(0 <= b && b < _n);
return leader(a) == leader(b);
}
int leader(int a) {
assert(0 <= a && a < _n);
if (parent_or_size[a] < 0) return a;
return parent_or_size[a] = leader(parent_or_size[a]);
}
int size(int a) {
assert(0 <= a && a < _n);
return -parent_or_size[leader(a)];
}
std::vector<std::vector<int>> groups() {
std::vector<int> leader_buf(_n), group_size(_n);
for (int i = 0; i < _n; i++) {
leader_buf[i] = leader(i);
group_size[leader_buf[i]]++;
}
std::vector<std::vector<int>> result(_n);
for (int i = 0; i < _n; i++) {
result[i].reserve(group_size[i]);
}
for (int i = 0; i < _n; i++) {
result[leader_buf[i]].push_back(i);
}
result.erase(
std::remove_if(result.begin(), result.end(),
[&](const std::vector<int> &v) { return v.empty(); }),
result.end());
return result;
}
private:
int _n;
// root node: -1 * component size
// otherwise: parent
std::vector<int> parent_or_size;
};
i32 construct_roads(std::vector<i32> _x, std::vector<i32> _y) {
int n = len(_x);
map<pair<int, int>, int> mp;
for (int i = 0; i < n; i++) {
mp[{_x[i], _y[i]}] = i;
}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
vec<pair<int, int>> edges;
for (int i = 0; i < n; i++) {
vec<pair<int, int>> moves = {{-2, 0},
{2, 0},
{0, -2},
{0, 2}};
for (auto [dx, dy]: moves) {
int nx = _x[i] + dx;
int ny = _y[i] + dy;
if (!mp.count({nx, ny})) continue;
edges.push_back({i, mp[{nx, ny}]});
}
}
for (int times = 0; times < 5; times++) {
DSU dsu(n);
shuffle(edges.begin(), edges.end(), rnd);
vec<pair<int, int>> used_edges;
for (auto [a, b]: edges) {
if (dsu.one(a, b)) continue;
dsu.unite(a, b);
used_edges.emplace_back(a, b);
}
if (dsu.size(0) != n) return 0;
shuffle(used_edges.begin(), used_edges.end(), rnd);
map<pair<int, int>, int> benches;
vec<pair<int, int>> benches_pos;
int idx = 0;
for (auto [a, b]: used_edges) {
auto [x1, y1] = pair<int, int>{_x[a], _y[a]};
auto [x2, y2] = pair<int, int>{_x[b], _y[b]};
if (x1 == x2) {
if (!benches.count({x1 - 1, (y1 + y2) / 2}))
benches[{x1 - 1, (y1 + y2) / 2}] = idx++, benches_pos.emplace_back(x1 - 1, (y1 + y2) / 2);
if (!benches.count({x1 + 1, (y1 + y2) / 2}))
benches[{x1 + 1, (y1 + y2) / 2}] = idx++, benches_pos.emplace_back(x1 + 1, (y1 + y2) / 2);
} else {
if (!benches.count({(x1 + x2) / 2, y1 - 1}))
benches[{(x1 + x2) / 2, y1 - 1}] = idx++, benches_pos.emplace_back((x1 + x2) / 2, y1 - 1);
if (!benches.count({(x1 + x2) / 2, y1 + 1}))
benches[{(x1 + x2) / 2, y1 + 1}] = idx++, benches_pos.emplace_back((x1 + x2) / 2, y1 + 1);
}
}
vec<vec<int>> g(n - 1 + len(benches));
int idt = 0;
for (auto [a, b]: used_edges) {
auto [x1, y1] = pair<int, int>{_x[a], _y[a]};
auto [x2, y2] = pair<int, int>{_x[b], _y[b]};
if (x1 == x2) {
g[idt].push_back(n - 1 + benches[{x1 - 1, (y1 + y2) / 2}]);
g[idt].push_back(n - 1 + benches[{x1 + 1, (y1 + y2) / 2}]);
} else {
g[idt].push_back(n - 1 + benches[{(x1 + x2) / 2, y1 - 1}]);
g[idt].push_back(n - 1 + benches[{(x1 + x2) / 2, y1 + 1}]);
}
idt++;
}
// matching
// shuffle
for (int i = 0; i < n - 1; i++) {
shuffle(g[i].begin(), g[i].end(), rnd);
}
vec<int> match(n - 1 + len(benches), -1);
vec<bool> used(n - 1 + len(benches), false);
function<bool(int)> dfs = [&](int v) -> bool {
if (used[v]) return false;
used[v] = true;
for (auto u: g[v]) {
if (match[u] == -1 || dfs(match[u])) {
match[u] = v;
match[v] = u;
return true;
}
}
return false;
};
bool flag = true;
do {
flag = false;
fill(used.begin(), used.end(), false);
for (int i = 0; i < n - 1; i++) {
if (match[i] == -1) {
if (dfs(i)) {
flag = true;
}
}
}
} while (flag);
int cnt = 0;
for (int i = 0; i < n - 1; i++) {
if (match[i] != -1) cnt++;
}
if (cnt == n - 1) {
vec<i32> x_benches, y_benches;
vec<i32> u, v;
for (int i = 0; i < n - 1; i++) {
x_benches.push_back(benches_pos[match[i] - n + 1].first);
y_benches.push_back(benches_pos[match[i] - n + 1].second);
u.push_back(used_edges[i].first);
v.push_back(used_edges[i].second);
}
build(u, v, x_benches, y_benches);
return 1;
}
}
return 0;
}
