#include "parks.h"
#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5 + 12;
int dsu[MAXN];
int set_of(int u) {
if(dsu[u] == u) return u;
return dsu[u] = set_of(dsu[u]);
}
void union_(int u, int v) {
dsu[set_of(u)] = set_of(v);
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
int n = x.size();
pair<pair<int, int>, int> p[n];
vector<int> stox = x, stoy = y;
for(int i=0; i<n; i++) {
p[i].first.first = x[i];
p[i].first.second = y[i];
p[i].second = i;
}
sort(p, p + n);
for(int i=0; i<n; i++) x[i] = stox[p[i].second], y[i] = stoy[p[i].second];
std::vector<int> u, v, a, b;
map<pair<int, int>, int> mp;
map<pair<int, int>, pair<int,int> > buh;
set<pair<int, int>> bench;
for(int i=0; i<n; i++) dsu[i] = i;
for(int i=0; i<n; i++) {
mp[{x[i], y[i]}] = i;
}
vector<pair<int,int>> edges;
for(int i=0; i<n; i++) {
if(mp.count({x[i] + 2, y[i]})) {
int U = i, V = mp[{x[i] + 2, y[i]}];
edges.push_back({U, V});
union_(U, V);
}
}
for(int i=0; i<n; i++) {
if(mp.count({x[i], y[i] + 2})) {
int U = i, V = mp[{x[i], y[i] + 2}];
if(set_of(U) != set_of(V)) {
edges.push_back({U, V});
union_(U, V);
if((x[i] + y[i]) % 4 == 2) {
bench.insert({x[i] - 1, y[i] + 1});
buh[{U, V}] = {x[i] - 1, y[i] + 1};
}
else {
bench.insert({x[i] + 1, y[i] + 1});
buh[{U, V}] = {x[i] + 1, y[i] + 1};
}
}
}
}
for(int i=0; i<n; i++) {
if(mp.count({x[i] + 2, y[i]})) {
int U = i, V = mp[{x[i] + 2, y[i]}];
if(!bench.count({x[i] + 1, y[i] - 1})) {
bench.insert({x[i] + 1, y[i] - 1});
buh[{U, V}] = {x[i] + 1, y[i] - 1};
}
else if(!bench.count({x[i] + 1, y[i] + 1})) {
bench.insert({x[i] + 1, y[i] + 1});
buh[{U, V}] = {x[i] + 1, y[i] + 1};
}
else return 0;
}
}
for(int i=1; i<n; i++) if(set_of(i) != set_of(i-1)) return 0;
for(auto x: edges) {
int U = x.first, V = x.second;
u.push_back(p[U].second);
v.push_back(p[V].second);
pair<int, int> wow = buh[{U, V}];
a.push_back(wow.first);
b.push_back(wow.second);
}
build(u, v, a, b);
return 1;
}
/*
#!/bin/bash
problem=parks
grader_name=grady
g++ -std=c++17 -O2 -o "${problem}" "${grader_name}.cpp" "${problem}.cpp"
./parks < input.txt
*/
