#include "parks.h"
#include <iostream>
using namespace std;
#define pb push_back
/*
IOI 2024 q3 FOUNTAIN PARKS
I'll try to get subtasks 1,2,3 for 30/100
*/
int n;
vector<int> visitted;
vector<int> lrow(100005, 0), mrow(100005, 0), rrow(100005, 0);
void dfs(int i, int row, int y){
cerr<<"#";
visitted[i]=1;
if(row==0){
if(lrow[y-1]!=0 && !visitted[lrow[y-1]]){ // check ABOVE
dfs(lrow[y-1], row, y-1);
}
if(mrow[y]!=0 && !visitted[mrow[y]]){ // chech RIGHT
dfs(mrow[y], row+1, y);
}
if(lrow[y+1]!=0 && !visitted[lrow[y+1]]){ // check BELOW
dfs(lrow[y+1], row, y+1);
}
} else if(row==1){
if(mrow[y-1]!=0 && !visitted[mrow[y-1]]){ // check ABOVE
dfs(mrow[y-1], row, y-1);
}
if(rrow[y]!=0 && !visitted[rrow[y]]){ // chech RIGHT
dfs(rrow[y], row+1, y);
}
if(mrow[y+1]!=0 && !visitted[mrow[y+1]]){ // check BELOW
dfs(mrow[y+1], row, y+1);
}
if(lrow[y]!=0 && !visitted[lrow[y]]){ // check LEFT
dfs(lrow[y], row-1, y);
}
} else if(row==2){
if(rrow[y-1]!=0 && !visitted[rrow[y-1]]){ // check ABOVE
dfs(rrow[y-1], row, y-1);
}
if(rrow[y+1]!=0 && !visitted[rrow[y+1]]){ // check BELOW
dfs(rrow[y+1], row, y+1);
}
if(mrow[y]!=0 && !visitted[mrow[y]]){ // check LEFT
dfs(mrow[y], row-1, y);
}
}
}
int construct_roads(vector<int> x, vector<int> y) {
n=x.size();
if (n == 1) {
build({}, {}, {}, {});
return 1;
}
vector<int> u, v, a, b;
// since all coordinates are even, we can compress by dividing everything by 2.
for(int i=0; i<n; i++){
if(x[i]>6)return 0;
if(x[i]==2){
lrow[y[i]/2] = i+1;
} else if(x[i]==4){
mrow[y[i]/2] = i+1;
} else if(x[i]==6){
rrow[y[i]/2] = i+1;
}
}
// start with a dfs to determine whether or not it is possible...
visitted = vector<int>(n+1, 0);
dfs(0, (x[0]/2)-1, y[0]/2);
for(int i=1; i<=n; i++) if(!visitted[i])return 0;
cerr<<"initial dfs passed!\n";
for(int y=0; y<100005; y++){
if(lrow[y]!=0 && lrow[y+1]!=0){
// far left (vertical)
u.pb(lrow[y]);
v.pb(lrow[y+1]);
// bench on the leftside
a.pb(1);
b.pb((2*y)+1);
}
if(rrow[y]!=0 && rrow[y+1]!=0){
// far right (vertical)
u.pb(rrow[y]);
v.pb(rrow[y+1]);
// bench on the rightside
a.pb(7);
b.pb((2*y)+1);
}
if(y%2==0){
// left side will face inside
if(mrow[y]!=0 && mrow[y+1]!=0){
u.pb(mrow[y]);
v.pb(mrow[y+1]);
a.pb(3);
b.pb((2*y)+1);
}
// right side will face up/down
if(mrow[y]!=0 && rrow[y]!=0 && (mrow[max(0,y-1)]==0 || rrow[max(0,y-1)]==0)){
// there should be a horizontal above.
u.pb(mrow[y]);
v.pb(rrow[y]);
a.pb(5);
b.pb((2*y)+1);
} else if(mrow[y+1]!=0 && rrow[y+1]!=0 && (mrow[y]==0 || rrow[y]==0)){
// " below
u.pb(mrow[y+1]);
v.pb(rrow[y+1]);
a.pb(5);
b.pb((2*y)+1);
}
} else{
// left side will face up/down
if(lrow[y]!=0 && mrow[y]!=0 && (lrow[max(0, y-1)]==0 || mrow[max(0,y-1)]==0)){
// there should be a horizontal above.
u.pb(lrow[y]);
v.pb(mrow[y]);
a.pb(3);
b.pb((2*y)+1);
} else if(lrow[y+1]!=0 && mrow[y+1]!=0 && (lrow[y]==0 || mrow[y]==0)){
// " below.
u.pb(lrow[y+1]);
v.pb(mrow[y+1]);
a.pb(3);
b.pb((2*y)+1);
}
// right side will face inside
if(mrow[y]!=0 && mrow[y+1]!=0){
u.pb(mrow[y]);
v.pb(mrow[y+1]);
a.pb(5);
b.pb((2*y)+1);
}
}
}
for(int i=0; i<v.size(); i++){
u[i]--;
v[i]--;
}
build(u, v, a, b);
return 1;
}
