#include "werewolf.h"
#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
#define chmax(x, v) x = max(x, v)
#define all(x) x.begin(), x.end()
using namespace std;
struct Req {
int depart, arrivee;
int borneInf, borneSup;
int iReq;
};
struct Noeud {
int id, fin;
bool operator < (const Noeud &autre) const {
return fin < autre.fin;
}
};
struct toLook {
int root, iReq;
};
const int N_NOEUDS = (1 << 19);
int nNoeuds, nAretes, nReqs;
vector<int> voisins[N_NOEUDS];
int ens[N_NOEUDS];
int getEns(int noeud){
if (ens[noeud] != noeud)
ens[noeud] = getEns(ens[noeud]);
return ens[noeud];
}
void initEns(){
for (int noeud = 0; noeud < nNoeuds; ++noeud)
ens[noeud] = noeud;
}
vector<int> enfants[2][N_NOEUDS];
vector<int> ancetres[2][N_NOEUDS];
int parcours[N_NOEUDS];
int prof[2][N_NOEUDS];
int deb[2][N_NOEUDS], fin[2][N_NOEUDS];
int temps = 0;
void dfs(int tour, int noeud, int etage){
prof[tour][noeud] = etage;
deb[tour][noeud] = temps++;
parcours[etage] = noeud;
for (int delta = 1; delta <= etage; delta *= 2)
ancetres[tour][noeud].pb(parcours[etage - delta]);
for (int enfant : enfants[tour][noeud])
dfs(tour, enfant, etage + 1);
fin[tour][noeud] = temps++;
}
void afficher(){
for (int i = 0; i < 2; ++i){
cout << "-------------\n";
for (int noeud = 0; noeud < nNoeuds; ++noeud){
cout << "NOEUD " << noeud << endl;
for (int enfant : enfants[i][noeud])
cout << enfant << " ";
cout << endl;
}
}
}
int debMax[N_NOEUDS * 2];
int getMax(int gauche, int droite){
//cout << "GET MAx " << gauche << " " << droite << endl;
if (droite < gauche) return -1;
if (gauche%2 == 1) return max(debMax[gauche], getMax(gauche + 1, droite));
if (droite%2 == 0) return max(debMax[droite], getMax(gauche, droite - 1));
return getMax(gauche/2, droite/2);
}
void update(int noeud, int val){
for (; noeud > 0; noeud /= 2)
chmax(debMax[noeud], val);
}
vector<toLook> aRegarder[N_NOEUDS];
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) {
nNoeuds = N;
nAretes = sz(X);
nReqs = sz(S);
for (int iArete = 0; iArete < nAretes; ++iArete){
voisins[X[iArete]].pb(Y[iArete]);
voisins[Y[iArete]].pb(X[iArete]);
}
vector<Req> reqs;
for (int iReq = 0; iReq < nReqs; ++iReq)
reqs.pb({S[iReq], E[iReq], L[iReq], R[iReq], iReq});
//Premier balayage : trouver ceux moins gros.
initEns();
for (int noeud = 0; noeud < nNoeuds; ++noeud)
for (int voisin : voisins[noeud]){
if (voisin < noeud){
int fus = getEns(voisin);
if (fus == noeud) continue;
enfants[0][noeud].pb(fus);
ens[fus] = noeud;
}
}
//Second balayage : trouver ceux plus gros.
initEns();
for (int noeud = nNoeuds - 1; noeud >= 0; --noeud)
for (int voisin : voisins[noeud]){
if (voisin > noeud){
int fus = getEns(voisin);
if (fus == noeud) continue;
enfants[1][noeud].pb(fus);
ens[fus] = noeud;
}
}
//afficher();
dfs(0, nNoeuds - 1, 0);
temps = 0;
dfs(1, 0, 0);
//Mettre les trucs biens.
for (Req& req : reqs){
//Fin arbre 0.
for (int iAncetre = sz(ancetres[0][req.arrivee]); iAncetre >= 0; --iAncetre){
if (iAncetre < sz(ancetres[0][req.arrivee]) && ancetres[0][req.arrivee][iAncetre] <= req.borneSup)
req.arrivee = ancetres[0][req.arrivee][iAncetre];
}
//Debut arbre 1.
for (int iAncetre = sz(ancetres[1][req.depart]); iAncetre >= 0; --iAncetre){
if (iAncetre < sz(ancetres[1][req.depart]) && ancetres[1][req.depart][iAncetre] >= req.borneInf)
req.depart = ancetres[1][req.depart][iAncetre];
}
aRegarder[req.arrivee].pb({req.depart, req.iReq});
//cout << "req " << req.depart << " " << req.arrivee << endl;
}
// afficher();
vector<int> res(nReqs); //TODO
vector<Noeud> noeuds;
for (int noeud = 0; noeud < nNoeuds; ++noeud)
noeuds.pb({noeud, fin[0][noeud]});
sort(all(noeuds));
// afficher();
for (Noeud noeud : noeuds){
//cout << noeud.id << endl;
update(N_NOEUDS + deb[1][noeud.id], deb[0][noeud.id]);
//cout << 42 << endl;
for (toLook req : aRegarder[noeud.id]){
//cout << "req " << req.root << " " << deb[1][req.root] << " " << fin[1][req.root] << endl;
int maxi = getMax(N_NOEUDS + deb[1][req.root], N_NOEUDS + fin[1][req.root]);
//cout << "lalala" << endl;
//cout << req.iReq << endl;
if (maxi >= deb[0][noeud.id])
res[req.iReq] = 1;
else
res[req.iReq] = 0;
}
}
return res;
}
