#include "parks.h"
#include <bits/stdc++.h>
using std::array;
using std::pair;
using std::tuple;
using std::vector;
template <class F>
struct fixed : private F {
explicit fixed(F&& f) : F(std::forward<F>(f)) {}
template <class... Args>
decltype(auto) operator()(Args&&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
struct UnionFind {
vector<int> data;
explicit UnionFind(const int n) : data(n, -1) {}
int find(const int u) {
return data[u] < 0 ? u : data[u] = find(data[u]);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
if (data[x] > data[y]) std::swap(x, y);
data[x] += data[y];
data[y] = x;
return true;
}
};
struct Points {
vector<pair<int, int>> pts;
std::map<pair<int, int>, int> map;
Points() : pts(), map() {}
int add_or_get(const pair<int, int>& p) {
if (const auto itr = map.find(p); itr != map.end()) {
return itr->second;
} else {
pts.push_back(p);
return map[p] = (int)pts.size() - 1;
}
}
int try_get(const pair<int, int>& p) const {
if (const auto itr = map.find(p); itr != map.end()) {
return itr->second;
} else {
return -1;
}
}
};
int construct_roads(vector<int> X, vector<int> Y) {
const int F = (int)X.size();
Points fountain, road, bench;
for (int i = 0; i < F; ++i) {
fountain.add_or_get({X[i], Y[i]});
}
vector<pair<int, int>> edges;
for (int i = 0; i < F; ++i) {
if (const int j = fountain.try_get({X[i] + 2, Y[i]}); j != -1) {
const int r = road.add_or_get({X[i] + 1, Y[i]});
if ((X[i] + Y[i]) % 4 == 0) {
const int b = bench.add_or_get({X[i] + 1, Y[i] + 1});
edges.emplace_back(r, b);
} else {
const int b = bench.add_or_get({X[i] + 1, Y[i] - 1});
edges.emplace_back(r, b);
}
}
if (const int j = fountain.try_get({X[i], Y[i] + 2}); j != -1) {
const int r = road.add_or_get({X[i], Y[i] + 1});
if ((X[i] + Y[i]) % 4 == 0) {
const int b = bench.add_or_get({X[i] - 1, Y[i] + 1});
edges.emplace_back(r, b);
} else {
const int b = bench.add_or_get({X[i] + 1, Y[i] + 1});
edges.emplace_back(r, b);
}
}
}
const int R = (int)road.pts.size();
const int B = (int)bench.pts.size();
vector<int> type(B), deg(B);
for (const auto& [r, b] : edges) {
deg[b] += 1;
}
for (int i = 0; i < B; ++i) {
const auto& [x, y] = bench.pts[i];
type[i] = (x / 2 + y / 2) % 2;
}
vector<char> use(R, true), visited(B);
const auto dfs = fixed([&](auto&& dfs, const int r, const int b) -> void {
if (b == -1 or deg[b] != 2 or visited[b]) {
return;
}
use[r] = false;
visited[b] = true;
const auto& [x, y] = bench.pts[b];
if (type[b] == 1) {
dfs(road.try_get({x, y - 1}), bench.try_get({x, y - 2}));
dfs(road.try_get({x, y + 1}), bench.try_get({x, y + 2}));
} else {
dfs(road.try_get({x - 1, y}), bench.try_get({x - 2, y}));
dfs(road.try_get({x + 1, y}), bench.try_get({x + 2, y}));
}
});
for (int src = 0; src < B; ++src) {
if (deg[src] == 2) {
const auto& [x, y] = bench.pts[src];
if (type[src] == 0) {
if (const int tmp = bench.try_get({x, y - 2}); tmp == -1 or deg[tmp] != 2) {
dfs(road.try_get({x, y - 1}), src);
}
if (const int tmp = bench.try_get({x, y + 2}); tmp == -1 or deg[tmp] != 2) {
dfs(road.try_get({x, y + 1}), src);
}
} else {
if (const int tmp = bench.try_get({x - 2, y}); tmp == -1 or deg[tmp] != 2) {
dfs(road.try_get({x - 1, y}), src);
}
if (const int tmp = bench.try_get({x + 2, y}); tmp == -1 or deg[tmp] != 2) {
dfs(road.try_get({x + 1, y}), src);
}
}
}
}
vector<int> match(R);
for (const auto& [r, b] : edges) {
if (use[r]) {
match[r] = b;
}
}
UnionFind dsu(F);
vector<int> u, v, a, b;
for (int i = 0; i < R; ++i) {
if (!use[i]) {
continue;
}
const auto& [x, y] = road.pts[i];
if (x % 2 == 1) {
const int s = fountain.try_get({x - 1, y});
const int t = fountain.try_get({x + 1, y});
if (dsu.merge(s, t)) {
u.push_back(s);
v.push_back(t);
a.push_back(bench.pts[match[i]].first);
b.push_back(bench.pts[match[i]].second);
}
} else {
const int s = fountain.try_get({x, y - 1});
const int t = fountain.try_get({x, y + 1});
if (dsu.merge(s, t)) {
u.push_back(s);
v.push_back(t);
a.push_back(bench.pts[match[i]].first);
b.push_back(bench.pts[match[i]].second);
}
}
}
if ((int)u.size() < F - 1) {
return 0;
}
build(u, v, a, b);
return 1;
}
