#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)
#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second
const long long BIG = 1000000000000000000LL;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vecInt;
const int borne = 201*1000;
// DSU
int repr[borne];
void initDsu()
{
form(i, borne) repr[i] = i;
}
int trouver(int x)
{
if (repr[x] != x) repr[x] = trouver(repr[x]);
return repr[x];
}
// Fin
int nbNoeuds, nbAretes, nbRequetes;
vecInt adj[borne];
vector<vecInt> arbreHumain;
vector<vecInt> arbreLoup;
vecInt seqHum, seqLoup;
vecInt parHum, parLoup;
vector<pii> tempsHum, tempsLoup;
void buildSeq(vector<vecInt> &arbre, vecInt &seq, vector<pii> &temps, int nod, int par)
{
temps[nod].fi = seq.size();
seq.push_back(nod);
for (int vo : arbre[nod]) if (vo != par) {
buildSeq(arbre, seq, temps, vo, nod);
}
temps[nod].se = seq.size();
seq.push_back(nod);
}
int traiter(int dep, int arr, int minHum, int maxLoup)
{
int subHum = dep;
int subLoup = arr;
while (parHum[subHum] != -1 && parHum[subHum] >= minHum) { subHum = parHum[subHum]; }
while (parLoup[subLoup] != -1 && parLoup[subLoup] <= maxLoup) { subLoup = parLoup[subLoup]; }
form2(i, tempsHum[subHum].fi, tempsHum[subHum].se) {
int vl = seqHum[i];
int tt = tempsLoup[vl].fi;
if (tempsLoup[subLoup].fi <= tt && tt <= tempsLoup[subLoup].se) { return 1; }
}
return 0;
}
vecInt check_validity(int N, vecInt X, vecInt Y, vecInt S, vecInt E, vecInt L, vecInt R)
{
nbNoeuds = N;
nbAretes = X.size();
nbRequetes = S.size();
vecInt A(nbRequetes);
arbreHumain.resize(N);
arbreLoup.resize(N);
parHum.resize(N);
parLoup.resize(N);
tempsHum.resize(N);
tempsLoup.resize(N);
form(i, nbAretes) {
int u = X[i], v = Y[i];
adj[u].push_back(v);
adj[v].push_back(u);
}
initDsu();
// Construire l'arbre humain (dans lequel les ensembles accessibles avec >= L[i] sont des sous-arbres)
ford(noeud, nbNoeuds) {
for (int voisin : adj[noeud]) if (voisin > noeud) {
voisin = trouver(voisin);
if (noeud != voisin) {
repr[voisin] = noeud;
arbreHumain[voisin].push_back(noeud);
arbreHumain[noeud].push_back(voisin);
parHum[voisin] = noeud;
}
}
}
initDsu();
// Construire l'arbre loup
form(noeud, nbNoeuds) {
for (int voisin : adj[noeud]) if (voisin < noeud) {
voisin = trouver(voisin);
if (noeud != voisin) {
repr[voisin] = noeud;
arbreLoup[voisin].push_back(noeud);
arbreLoup[noeud].push_back(voisin);
parLoup[voisin] = noeud;
}
}
}
parHum[0] = -1;
parLoup[nbNoeuds-1] = -1;
buildSeq(arbreHumain, seqHum, tempsHum, 0, -1);
buildSeq(arbreLoup, seqLoup, tempsLoup, nbNoeuds-1, -1);
form(i, nbRequetes) {
A[i] = traiter(S[i], E[i], L[i], R[i]);
}
return A;
}
