#include "parks.h"
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;
int N;
vector<pair<int, int > >node;
map<pair<int, int>, int>mp;
vector<int>u, v, a, b;
int padre[200005];
int findPadre(int k){
if(padre[k] == k)return k;
return padre[k] = findPadre(padre[k]);
}
void unir(int p, int q){
p = findPadre(p);
q = findPadre(q);
if(p == q){
return;
}
padre[p] = q;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
N = x.size();
for(int i = 0 ; i < N ; i ++){
node.pb({x[i], y[i]});
mp[{x[i], y[i]}] = i;
padre[i] = i;
}
queue<int>fila;
fila.push(0);
int current;
while(!fila.empty()){
current = fila.front();
fila.pop();
pair<int, int > derecha = {node[current].ff+2, node[current].ss}, izquierda = {node[current].ff-2, node[current].ss}, abajo = {node[current].ff, node[current].ss-2}, arriba = {node[current].ff, node[current].ss+2};
vector<pair<int, int> >porRecorrer;
porRecorrer.pb(izquierda);
porRecorrer.pb(arriba);
porRecorrer.pb(derecha);
porRecorrer.pb(abajo);
for(pair<int, int> siguiente : porRecorrer){
if(!mp.count(siguiente))continue;
int indxnxt = mp[siguiente];
if(findPadre(indxnxt) == findPadre(0))continue; //(No va a pasar)
unir(indxnxt, current);
u.pb(current);
v.pb(indxnxt);
//cout << "se une " << current <<" con " << indxnxt << endl;
fila.push(indxnxt);
}
}
for(int i =0 ; i < N ; i ++){
if(findPadre(i) != findPadre(0)){
//cout << "padre de " <<i << "!= padre de " << 0 << "(" << findPadre(i) << "!=" << findPadre(0) << ")" << endl;
return 0;
}
}
map<pair<int, int >, int > coordenadasUsadas;
vector<int>mientrasA, mientrasB;
int prioridad;
bool seLogro = true;
for(int i = 0 ; i < v.size() ; i++){
if(node[v[i]].ff == node[u[i]].ff){//vertical
pair<int, int > izquierdo = {node[v[i]].ff-1, (node[v[i]].ss+node[u[i]].ss) / 2}, derecho = {node[v[i]].ff+1, (node[v[i]].ss+node[u[i]].ss) / 2};
if(!coordenadasUsadas.count(izquierdo)){
mientrasA.pb(izquierdo.ff);
mientrasB.pb(izquierdo.ss);
//cout << " probando (" << izquierdo.ff << ", " << izquierdo.ss << ") para la union numero " << i << endl;
coordenadasUsadas[izquierdo] = i;
}else if(!coordenadasUsadas.count(derecho)){
mientrasA.pb(derecho.ff);
mientrasB.pb(derecho.ss);
//cout << " probando (" << derecho.ff << ", " << derecho.ss << ") para la union numero " << i << endl;
coordenadasUsadas[derecho] = i;
}else{
seLogro = false;
prioridad = i;
//cout << "Paila, reintentando desde " << prioridad;
break;
}
}else{ // horizontal
pair<int, int > arriba = {(node[v[i]].ff+node[u[i]].ff) / 2, node[v[i]].ss+1}, abajo = {(node[v[i]].ff+node[u[i]].ff) / 2, node[v[i]].ss-1};
if(!coordenadasUsadas.count(arriba)){
mientrasA.pb(arriba.ff);
mientrasB.pb(arriba.ss);
//cout << " probando (" << arriba.ff << ", " << arriba.ss << ") para la union numero " << i << endl;
coordenadasUsadas[arriba] = i;
}else if(!coordenadasUsadas.count(abajo)){
mientrasA.pb(abajo.ff);
mientrasB.pb(abajo.ss);
//cout << " probando (" << abajo.ff << ", " << abajo.ss << ") para la union numero " << i << endl;
coordenadasUsadas[abajo] = i;
}else{
seLogro = false;
prioridad = i;
//cout << "Paila, reintentando desde " << prioridad;
break;
}
}
}
if(seLogro){
build(u, v, mientrasA, mientrasB);
return 1;
}else{
for(int i = 0 ; i < v.size() ; i ++){
a.pb(0);
b.pb(0);
}
coordenadasUsadas.clear();
if(node[v[prioridad]].ff == node[u[prioridad]].ff){//vertical
pair<int, int > izquierdo = {node[v[prioridad]].ff-1, (node[v[prioridad]].ss+node[u[prioridad]].ss) / 2}, derecho = {node[v[prioridad]].ff+1, (node[v[prioridad]].ss+node[u[prioridad]].ss) / 2};
if(!coordenadasUsadas.count(izquierdo)){
a[prioridad] = izquierdo.ff;
b[prioridad] = izquierdo.ss;
coordenadasUsadas[izquierdo] = prioridad;
}else if(!coordenadasUsadas.count(derecho)){
a[prioridad] = derecho.ff;
b[prioridad] = derecho.ss;
coordenadasUsadas[derecho] = prioridad;
}else{
seLogro = false;
prioridad = prioridad;
return 0;
}
}else{ // horizontal
pair<int, int > arriba = {(node[v[prioridad]].ff+node[u[prioridad]].ff) / 2, node[v[prioridad]].ss+1}, abajo = {(node[v[prioridad]].ff+node[u[prioridad]].ff) / 2, node[v[prioridad]].ss-1};
if(!coordenadasUsadas.count(arriba)){
a[prioridad] = arriba.ff;
b[prioridad] = arriba.ss;
coordenadasUsadas[arriba] = prioridad;
}else if(!coordenadasUsadas.count(abajo)){
a[prioridad] = abajo.ff;
b[prioridad] = abajo.ss;
coordenadasUsadas[abajo] = prioridad;
}else{
seLogro = false;
prioridad = prioridad;
return 0;
}
}
//cout << "en prioridad se unió en " << a[prioridad] <<", " << b[prioridad] << endl;
for(int i = 0 ; i < v.size() ; i++){
if(i==prioridad)continue;
if(node[v[i]].ff == node[u[i]].ff){//vertical
pair<int, int > izquierdo = {node[v[i]].ff-1, (node[v[i]].ss+node[u[i]].ss) / 2}, derecho = {node[v[i]].ff+1, (node[v[i]].ss+node[u[i]].ss) / 2};
if(!coordenadasUsadas.count(izquierdo)){
a[prioridad] = izquierdo.ff;
b[prioridad] = izquierdo.ss;
coordenadasUsadas[izquierdo] = i;
}else if(!coordenadasUsadas.count(derecho)){
a[prioridad] = derecho.ff;
b[prioridad] = derecho.ss;
coordenadasUsadas[derecho] = i;
}else{
seLogro = false;
prioridad = i;
return 0;
}
}else{ // horizontal
pair<int, int > arriba = {(node[v[i]].ff+node[u[i]].ff) / 2, node[v[i]].ff+1}, abajo = {(node[v[i]].ff+node[u[i]].ff) / 2, node[v[i]].ff-1};
if(!coordenadasUsadas.count(arriba)){
a[prioridad] = arriba.ff;
b[prioridad] = arriba.ss;
coordenadasUsadas[arriba] = i;
}else if(!coordenadasUsadas.count(abajo)){
a[prioridad] = abajo.ff;
b[prioridad] = abajo.ss;
coordenadasUsadas[abajo] = i;
}else{
seLogro = false;
prioridad = i;
//cout << "Paila, no se pudo en " << i << endl;
return 0;
}
}
//cout <<"la union " << i << "se unio en " << mientrasA.back() << ", " << mientrasB.back() << endl;
}
build(u, v, a, b);
return 1;
}
}
