#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
const int NMAX = 200000;
vector<int> chemins[NMAX];
int dejaVu[2][NMAX];
int iDejaVu;
bool possible(int noeud, int fin, int interditHomme, int interditLoup, bool etat)
{
if(dejaVu[etat][noeud] == iDejaVu)
return false;
dejaVu[etat][noeud] = iDejaVu;
if(etat == 0)
{
if(noeud < interditHomme) {
//cout << noeud << " " << etat << " : " << false << endl;
return false;
}
if(possible(noeud, fin, interditHomme, interditLoup, 1))
{
//cout << noeud << " " << etat << " : " << true << endl;
return true;
}
}
else if(noeud > interditLoup) {
//cout << noeud << " " << etat << " : " << false << endl;
return false;
}
if((noeud == fin) && (etat == 1)) {
//cout << noeud << " " << etat << " : " << true << endl;
return true;
}
for(auto pro : chemins[noeud])
{
if(possible(pro, fin, interditHomme, interditLoup, etat)) {
//cout << noeud << " " << etat << " : " << true << endl;
return true;
}
}
//cout << noeud << " " << etat << " : " << false << endl;
return false;
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y,
std::vector<int> S, std::vector<int> E,
std::vector<int> L, std::vector<int> R) {
int nbNoeuds = N, nbChemins = X.size();
iDejaVu = 1;
for(int i = 0; i < nbChemins; i++)
{
chemins[X[i]].push_back(Y[i]);
chemins[Y[i]].push_back(X[i]);
}
int Q = S.size();
std::vector<int> A(Q);
for (int i = 0; i < Q; ++i) {
//cout << "deb " << S[i] << " " << E[i] << " " << L[i] << " " << R[i] << endl;
A[i] = possible(S[i], E[i], L[i], R[i], 0);
iDejaVu++;
}
return A;
}
