#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
int ufs[200005];
int ge(int x) {
if (ufs[x] == -1)
return x;
return ufs[x] = ge(ufs[x]);
}
vector<pair<int, int>> pts;
map<pair<int, int>, int> idx;
vector<pair<int, int>> elist;
int n;
mt19937 rng(108616);
vector<int> bpt[200005];
int mach[800005];
int vis[200005];
int gloti = 0;
bool dfs(int u, int ti) {
vis[u] = ti;
for (int v : bpt[u]) {
if (mach[v] == -1 || ((vis[mach[v]] != ti) && dfs(mach[v], ti))) {
mach[v] = u;
return 1;
}
}
return 0;
}
bool hasmxm(int cnt) {
for (int i = 0; i < cnt; i++) {
gloti++;
if (!dfs(i, gloti))
return 0;
}
return 1;
}
bool ranAttempt() {
shuffle(elist.begin(), elist.end(), rng);
memset(ufs, -1, sizeof ufs);
vector<pair<int, int>> mst;
for (auto [u, v] : elist) {
if (ge(u) != ge(v)) {
ufs[ge(u)] = ge(v);
mst.push_back({u, v});
}
}
if (mst.size() != n - 1)
return 0;
map<pair<int, int>, int> benches;
int edid = 0, beid = 0;
for (auto [u, v] : mst) {
auto [x1, y1] = pts[u];
auto [x2, y2] = pts[v];
bpt[edid].clear();
if (x1 == x2) {
int c = min(y1, y2);
pair<int, int> p1 = {x1 - 1, c + 1}, p2 = {x1 + 1, c + 1};
if (!benches.count(p1))
benches[p1] = beid++;
if (!benches.count(p2))
benches[p2] = beid++;
bpt[edid].push_back(benches[p1]);
bpt[edid].push_back(benches[p2]);
} else {
int c = min(x1, x2);
pair<int, int> p1 = {c + 1, y1 + 1}, p2 = {c + 1, y1 - 1};
if (!benches.count(p1))
benches[p1] = beid++;
if (!benches.count(p2))
benches[p2] = beid++;
bpt[edid].push_back(benches[p1]);
bpt[edid].push_back(benches[p2]);
}
edid++;
}
for (int i = 0; i < beid; i++)
mach[i] = -1;
if (hasmxm(edid)) {
vector<int> U, V;
vector<int> mx(mst.size()), my(mst.size());
for (auto [u, v] : mst) {
U.push_back(u);
V.push_back(v);
}
for (auto [x, i] : benches) {
if (mach[i] == -1)
continue;
auto [zx, zy] = x;
mx[mach[i]] = zx;
my[mach[i]] = zy;
}
build(U, V, mx, my);
return 1;
}
return 0;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
n = x.size();
pts = vector<pair<int, int>>(n);
for (int i = 0; i < n; i++) {
pts[i] = {x[i], y[i]};
idx[pts[i]] = i;
}
for (int i = 0; i < n; i++) {
if (idx.count({x[i] + 2, y[i]}))
elist.push_back({i, idx[{x[i] + 2, y[i]}]});
if (idx.count({x[i], y[i] + 2}))
elist.push_back({i, idx[{x[i], y[i] + 2}]});
}
while (clock() < 3 * CLOCKS_PER_SEC) {
if (ranAttempt())
return 1;
}
return 0;
}
