#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
struct Coord {
int x, y, i;
bool operator<(Coord other) const {
if (y == other.y) {
return x < other.x;
}
return y < other.y;
}
};
int n;
vector<Coord> coords;
std::vector<int> u, v, a, b;
vector<int> link;
int find(int x) {
if (link[x] != x) link[x] = find(link[x]);
return link[x];
}
void unite(int a, int b) {
int x = find(a), y = find(b);
link[x] = y;
}
bool same(int a, int b) {
return find(a) == find(b);
}
void connect(int i, int j) {
if (coords[i].x == coords[j].x) {
u.pb(coords[i].i);
v.pb(coords[j].i);
if (coords[i].x == 4)
a.pb(coords[i].x+1);
else
a.pb(coords[i].x-1);
b.pb(coords[i].y+1);
} else if (coords[i].y == coords[j].y) {
u.pb(coords[i].i);
v.pb(coords[j].i);
a.pb(coords[i].x+1);
b.pb(coords[i].y-1);
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
n = x.size();
int maxX = 0;
for (int i = 0; i < n; i++) maxX = max(maxX, x[i]);
bool res = true;
if (maxX <= 4) {
coords = vector<Coord>(n);
for (int i = 0; i < n; i++) {
coords[i] = {x[i], y[i], i};
}
sort(coords.begin(), coords.end());
link = vector<int>(n);
iota(link.begin(), link.end(), 0);
for (int i = 0; i < n-1; i++) {
if ((coords[i].y+2 == coords[i+1].y && coords[i].x == coords[i+1].x) || (coords[i].y == coords[i+1].y && abs(coords[i+1].x-coords[i].x) == 2)) {
connect(i, i+1);
unite(i, i+1);
}
if (i+2 < n && ((coords[i].y+2 == coords[i+2].y && coords[i].x == coords[i+2].x) || (coords[i].y == coords[i+2].y && abs(coords[i+2].x-coords[i].x) == 2))) {
connect(i, i+2);
unite(i, i+2);
}
}
for (int i = 0; i < n-1; i++) {
res &= find(i) == find(i+1);
}
} else {
int maxY = 0;
for (int i = 0; i < n; i++) maxY = max(maxY, y[i]);
link = vector<int>(n);
iota(link.begin(), link.end(), 0);
vector<vector<int>> mat(maxY/2, vector<int>(3)), matIdx(maxY/2, vector<int>(3));
for (int i = 0; i < n; i++) {
mat[y[i]/2-1][x[i]/2-1] = 1;
matIdx[y[i]/2-1][x[i]/2-1] = i;
}
map<int, map<int, int>> bench;
for (int i = 0; i < maxY/2; i++) {
if (mat[i][0] && mat[i][1]) {
if (bench[3][2*i+1]) {
if (!same(matIdx[i][0], matIdx[i][1])) {
if (bench[3][2*i+3]) res = false;
u.pb(matIdx[i][0]);
v.pb(matIdx[i][1]);
a.pb(3);
b.pb(2*i+3);
unite(matIdx[i][0], matIdx[i][1]);
}
} else {
u.pb(matIdx[i][0]);
v.pb(matIdx[i][1]);
a.pb(3);
b.pb(2*i+1);
unite(matIdx[i][0], matIdx[i][1]);
}
if (a.size()) {
bench[a[a.size()-1]][b[b.size()-1]] = true;
}
}
if (mat[i][1] && mat[i][2]) {
if (bench[5][2*i+1]) {
if (!same(matIdx[i][1], matIdx[i][2])) {
if (bench[5][2*i+3]) res = false;
u.pb(matIdx[i][1]);
v.pb(matIdx[i][2]);
a.pb(5);
b.pb(2*i+3);
unite(matIdx[i][1], matIdx[i][2]);
}
} else {
u.pb(matIdx[i][1]);
v.pb(matIdx[i][2]);
a.pb(5);
b.pb(2*i+1);
unite(matIdx[i][1], matIdx[i][2]);
}
if (a.size()) {
bench[a[a.size()-1]][b[b.size()-1]] = true;
}
}
if (i == maxY/2-1) continue;
bool isValid = false;
if (mat[i][0] && mat[i+1][0]) {
u.pb(matIdx[i][0]);
v.pb(matIdx[i+1][0]);
a.pb(1);
b.pb(2*i+3);
unite(matIdx[i][0], matIdx[i+1][0]);
isValid = true;
if (a.size()) {
bench[a[a.size()-1]][b[b.size()-1]] = true;
}
}
if (mat[i][2] && mat[i+1][2]) {
u.pb(matIdx[i][2]);
v.pb(matIdx[i+1][2]);
a.pb(7);
b.pb(2*i+3);
unite(matIdx[i][2], matIdx[i+1][2]);
isValid = true;
if (a.size()) {
bench[a[a.size()-1]][b[b.size()-1]] = true;
}
}
if (!isValid && mat[i][1] && mat[i+1][1]) {
u.pb(matIdx[i][1]);
v.pb(matIdx[i+1][1]);
if (!bench[3][2*i+3])
a.pb(3);
else if (!bench[5][2*i+3])
a.pb(5);
else
res = false;
b.pb(2*i+3);
unite(matIdx[i][1], matIdx[i+1][1]);
if (a.size()) {
bench[a[a.size()-1]][b[b.size()-1]] = true;
}
}
}
for (int i = 0; i < n-1; i++) {
res &= find(i) == find(i+1);
}
}
if (!res) return 0;
build(u, v, a, b);
return 1;
}
