#include "werewolf.h"
#include "bits/stdc++.h"
using namespace std;
vector< vector<int> > Grafo, Visitados;
vector< vector< pair<int, int> > > Mesa_dispersa_menor, Mesa_dispersa_mayor;
vector<int> Orden, iOrden;
vector<bool> Visitadoss;
int Tiempo = 0, Inicio, Final;
struct Responder_esto{
int Mayor, Menor;
};
struct Consultita{
int Inicio, Final, Izquierda, Derecha, _ndice;
};
bool operator<(const Consultita& a, const Consultita& b){
if(a.Izquierda < b.Izquierda) return 1;
if(b.Izquierda < a.Izquierda) return 0;
if(a.Derecha < b.Derecha) return 1;
if(b.Derecha < a.Derecha) return 0;
return a._ndice < b._ndice;
}
void Crear(int Nodo, int Anterior){
//cerr<<Nodo<<" "<<Anterior<<"\n";
Orden[Nodo] = Tiempo;
iOrden[Tiempo] = Nodo;
Visitadoss[Nodo] = 1;
Tiempo++;
if(Anterior != -2){
Mesa_dispersa_menor[Nodo].push_back({min(Nodo, Anterior), Anterior});
Mesa_dispersa_mayor[Nodo].push_back({max(Nodo, Anterior), Anterior});
for(int i = 0; i < Mesa_dispersa_mayor[Anterior].size(); i++){
Mesa_dispersa_menor[Nodo].push_back({min(Mesa_dispersa_menor[Nodo].back().first, Mesa_dispersa_menor[Anterior][i].first), Mesa_dispersa_menor[Anterior][i].second});
Mesa_dispersa_mayor[Nodo].push_back({max(Mesa_dispersa_mayor[Nodo].back().first, Mesa_dispersa_mayor[Anterior][i].first), Mesa_dispersa_mayor[Anterior][i].second});
Anterior = Mesa_dispersa_mayor[Anterior][i].second;
}
}
for(auto E: Grafo[Nodo]) if(E != Anterior and !Visitadoss[E]) Crear(E, Nodo);
}
Responder_esto Consulta(int I, int D){
if(Orden[D] < Orden[I]) swap(I, D);
int Menor = 22222222, Mayor = -2;
Responder_esto Respuesta;
if(I == D){
Respuesta.Mayor = I;
Respuesta.Menor = D;
return Respuesta;
}
while(I != D){
//cerr<<I<<" "<<D<<"\n";
int i = 0, d = Mesa_dispersa_menor[D].size() - 1, m = 0;
while(1){
int p = (i + d) / 2;
if(Orden[Mesa_dispersa_menor[D][p].second] < Orden[I]){
d = p - 1;
} else {
i = p + 1;
m = p;
}
if(i >= d + 1) break;
}
Mayor = max(Mayor, Mesa_dispersa_mayor[D][m].first);
Menor = min(Menor, Mesa_dispersa_menor[D][m].first);
D = Mesa_dispersa_mayor[D][m].second;
}
Respuesta.Mayor = Mayor;
Respuesta.Menor = Menor;
return Respuesta;
}
bool Bien(int Nodo, int Objetivo, bool Humano, int No_humano, int No_lobo){
if(Nodo == Objetivo and (!Humano or (Nodo >= No_humano and Nodo <= No_lobo))) return 1;
if((Nodo < No_humano and Humano) or (Nodo > No_lobo and !Humano)) return 0;
Visitados[Nodo][Humano] = 1;
bool r = 0;
for(auto E: Grafo[Nodo]){
if(!Visitados[E][Humano]) r = r or Bien(E, Objetivo, Humano, No_humano, No_lobo);
if(Nodo >= No_humano and Nodo <= No_lobo and Humano) r = r or Bien(E, Objetivo, 0, No_humano, No_lobo);
}
return r;
}
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r){
int q = s.size(), m = x.size();
vector<int> a(q);
Grafo.assign(n, {});
Visitadoss.assign(n, 0);
vector<int> Grado(n, -0);
bool L_nea = 1;
for(int i = 0; i < m; i++){
Grafo[x[i]].push_back(y[i]);
Grafo[y[i]].push_back(x[i]);
Grado[x[i]]++;
Grado[y[i]]++;
if(Grado[x[i]] > 2 or Grado[y[i]] > 2) L_nea = -0;
if(Grado[x[i]] == 1) Inicio = x[i];
if(Grado[y[i]] == 1) Inicio = y[i];
}
if(L_nea){
Orden.assign(n, 0);
iOrden.assign(n, 0);
Mesa_dispersa_menor.assign(n, vector< pair<int, int> >());
Mesa_dispersa_mayor.assign(n, vector< pair<int, int> >());
Crear(Inicio, -2);
//cerr<<"Creado.\n";
for(int i = 0; i < q; i++){
//cerr<<i<<" "<<Orden[s[i]]<<" "<<Orden[e[i]]<<"\n";
if(Orden[s[i]] < Orden[e[i]]){
int Izquierda = Orden[s[i]], Derecha = n - 1, Mejor = Orden[s[i]];
while(1){
int Promedio = (Izquierda + Derecha) / 2;
if(Consulta(s[i], iOrden[Promedio]).Menor >= l[i]){
Mejor = Promedio;
Izquierda = Promedio + 1;
} else Derecha = Promedio - 1;
if(Izquierda >= Derecha + 1) break;
}
Izquierda = -0, Derecha = Orden[e[i]];
int Otro_mejor = Orden[e[i]];
while(1){
int Promedio = (Izquierda + Derecha) / 2;
if(Consulta(e[i], iOrden[Promedio]).Mayor <= r[i]){
Mejor = Promedio;
Derecha = Promedio - 1;
} else Izquierda = Promedio + 1;
if(Izquierda >= Derecha + 1) break;
}
a[i] = Orden[Mejor] >= Orden[Otro_mejor];
} else {
int Izquierda = 0, Derecha = Orden[s[i]], Mejor = Orden[s[i]];
while(1){
int Promedio = (Izquierda + Derecha) / 2;
if(Consulta(s[i], iOrden[Promedio]).Menor >= l[i]){
Mejor = Promedio;
Derecha = Promedio - 1;
} else Izquierda = Promedio + 1;
if(Izquierda >= Derecha + 1) break;
}
Izquierda = Orden[e[i]], Derecha = n - 1;
int Otro_mejor = Orden[e[i]];
while(1){
int Promedio = (Izquierda + Derecha) / 2;
if(Consulta(e[i], iOrden[Promedio]).Mayor <= r[i]){
Mejor = Promedio;
Izquierda = Promedio + 1;
} else Derecha = Promedio - 1;
if(Izquierda >= Derecha + 1) break;
}
a[i] = Orden[Mejor] <= Orden[Otro_mejor];
}
}
return a;
/*vector<Consultita> Lista(q);
for(int i = 0; i < n; i++){
Consultita Hola;
Hola.Derecha = r[i];
Hola.Final = e[i];
Hola.Inicio = s[i];
Hola.Izquierda = l[i];
Hola._ndice = i;
Lista[i] = Hola;
}
sort(Lista.begin(), Lista.end());
Recién me di cuenta de que se pueden hacer las consultas en línea.*/
}
for(int i = 0; i < q; i++){
Visitados.assign(n, vector<int>(2, 0));
a[i] = Bien(s[i], e[i], 1, l[i], r[i]) or (Bien(s[i], e[i], 0, l[i], r[i]) and s[i] >= l[i] and s[i] <= r[i]);
}
return a;
}
