#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
template<int NB_NOEUDS>
class UnionFind
{
public:
UnionFind ()
{
for (int iNoeud=0; iNoeud<NB_NOEUDS; iNoeud++) {
representants[iNoeud] = iNoeud;
tailles[iNoeud] = 1;
}
}
int representant (const int iNoeud)
{
if (representants[iNoeud] == iNoeud) {
return iNoeud;
}
return representants[iNoeud] = representant(representants[iNoeud]);
}
int taille (const int iNoeud)
{
return tailles[representant(iNoeud)];
}
void unir (int iNoeud1, int iNoeud2)
{
iNoeud1 = representant(iNoeud1);
iNoeud2 = representant(iNoeud2);
if (iNoeud1 == iNoeud2) {
return;
}
tailles[iNoeud1] += tailles[iNoeud2];
tailles[iNoeud2] = 0;
representants[iNoeud2] = iNoeud1;
}
private:
int representants[NB_NOEUDS];
int tailles[NB_NOEUDS]; // Valide uniquement pour les racines
};
const int NB_FORMES = 2;
const int FORME_HUMAINE = 0;
const int FORME_LOUP = 1;
const int NB_MAX_NOEUDS = 200*1000;
struct Noeud
{
vector<int> voisins;
};
int nbNoeuds;
Noeud noeuds[NB_MAX_NOEUDS];
/*
* Arbres
*/
struct NoeudArbre
{
int parents[22];
vector<int> enfants;
int debut, fin;
NoeudArbre () :
debut(-1), fin(-1)
{
fill(parents, parents+22, -1);
}
};
UnionFind<NB_MAX_NOEUDS> unionfind;
NoeudArbre arbres[NB_FORMES][NB_MAX_NOEUDS];
void genererArbre (const int forme)
{
unionfind = UnionFind<NB_MAX_NOEUDS> ();
for (int iIteration=0; iIteration<nbNoeuds; iIteration++) {
const int iNoeud = forme == FORME_LOUP ? iIteration : nbNoeuds-iIteration-1;
const Noeud &noeud = noeuds[iNoeud];
for (int iVoisin : noeud.voisins) {
// Si le voisin est déjà dans l'arbre
if ((forme == FORME_LOUP && iVoisin < iNoeud) || (forme == FORME_HUMAINE && iVoisin > iNoeud)) {
if (unionfind.representant(iNoeud) != unionfind.representant(iVoisin)) {
arbres[forme][iNoeud].enfants.push_back( unionfind.representant(iVoisin) );
arbres[forme][unionfind.representant(iVoisin)].parents[0] = iNoeud;
unionfind.unir(iNoeud, iVoisin);
}
}
}
}
}
int calculerIntervalles (const int iNoeud, const int forme) // --> nbDescendants (noeud actuel inclus)
{
NoeudArbre &noeud = arbres[forme][iNoeud];
int nbDescendants = 1;
for (int enfant : noeud.enfants) {
arbres[forme][enfant].debut = noeud.debut + nbDescendants;
nbDescendants += calculerIntervalles(enfant, forme);
}
noeud.fin = noeud.debut + nbDescendants;
return nbDescendants;
}
// Lors de l'appel, les parents des parents du noeud sont déjà à jour
void calculerParents (const int iNoeud, const int forme)
{
NoeudArbre &noeud = arbres[forme][iNoeud];
for (int iEtape=1; noeud.parents[iEtape-1] != -1; iEtape++) {
noeud.parents[iEtape] = arbres[forme][ noeud.parents[iEtape-1] ].parents[iEtape-1];
}
}
/*
* Arbre binaire
*/
struct ArbreBinaire
{
static const int PROFONDEUR = 18;
static const int PREMIERE_FEUILLE = 1<<PROFONDEUR;
static const int NB_NOEUDS = 2*PREMIERE_FEUILLE;
ArbreBinaire ()
{
fill(noeuds, noeuds+NB_NOEUDS, 0);
}
void incrementer (const int pos)
{
int iNoeud = PREMIERE_FEUILLE + pos;
while (iNoeud >= 1) {
noeuds[iNoeud]++;
iNoeud /= 2;
}
}
int getSomme (const int debut, const int fin,
const int iNoeudActuel=1, const int debutActuel=0, const int finActuelle=PREMIERE_FEUILLE)
{
if (debutActuel >= debut && finActuelle <= fin) {
return noeuds[iNoeudActuel];
}
if (finActuelle <= debut || debutActuel >= fin) {
return 0;
}
const int milieuActuel = (debutActuel+finActuelle) / 2;
return getSomme(debut, fin, iNoeudActuel*2, debutActuel, milieuActuel)
+ getSomme(debut, fin, iNoeudActuel*2+1, milieuActuel, finActuelle);
}
int noeuds[NB_NOEUDS];
};
ArbreBinaire arbreBinaire;
/*
* Balayage
*/
struct Evenement
{
int date;
bool estIntervalle;
int debut, fin;
int iRequete;
bool operator< (const Evenement &autre) const
{
if (date != autre.date) {
return date < autre.date;
}
if (estIntervalle != autre.estIntervalle) {
return estIntervalle;
}
if (debut != autre.debut) {
return debut < autre.debut;
}
if (fin != autre.fin) {
return fin < autre.fin;
}
return iRequete < autre.iRequete;
}
};
int getRacineAccessible (const int forme, const int iNoeud, const int seuil)
{
int iEtape = 21;
while (iEtape >= 0 &&
(arbres[forme][iNoeud].parents[iEtape] == -1
|| (forme == FORME_HUMAINE ? arbres[forme][iNoeud].parents[iEtape] < seuil : arbres[forme][iNoeud].parents[iEtape] > seuil))) {
iEtape--;
}
if (iEtape == -1) {
return iNoeud;
}
return getRacineAccessible(forme, arbres[forme][iNoeud].parents[iEtape], seuil);
}
vector<int> check_validity (int nbNoeuds_, vector<int> noeuds1Arretes, vector<int> noeuds2Arretes,
vector<int> villesDeparts, vector<int> villesArrivees,
vector<int> seuilsBas, vector<int> seuilsHauts )
{
nbNoeuds = nbNoeuds_;
for (int iArrete=0; iArrete<(int)noeuds1Arretes.size(); iArrete++) {
noeuds[noeuds1Arretes[iArrete]].voisins.push_back(noeuds2Arretes[iArrete]);
noeuds[noeuds2Arretes[iArrete]].voisins.push_back(noeuds1Arretes[iArrete]);
}
const int nbRequetes = villesDeparts.size();
genererArbre(FORME_HUMAINE);
genererArbre(FORME_LOUP);
int debutActuel = 0;
for (int iNoeud=0; iNoeud<nbNoeuds; iNoeud++) {
if (arbres[FORME_HUMAINE][iNoeud].fin == -1) {
arbres[FORME_HUMAINE][iNoeud].debut = debutActuel;
debutActuel += calculerIntervalles(iNoeud, FORME_HUMAINE);
}
calculerParents(iNoeud, FORME_HUMAINE);
}
debutActuel = 0;
for (int iNoeud=nbNoeuds-1; iNoeud>=0; iNoeud--) {
if (arbres[FORME_LOUP][iNoeud].fin == -1) {
arbres[FORME_LOUP][iNoeud].debut = debutActuel;
debutActuel += calculerIntervalles(iNoeud, FORME_LOUP);
}
calculerParents(iNoeud, FORME_LOUP);
}
vector<Evenement> evenements;
for (int iNoeud=0; iNoeud<nbNoeuds; iNoeud++) {
const int pos1 = arbres[FORME_HUMAINE][iNoeud].debut;
const int pos2 = arbres[FORME_LOUP][iNoeud].debut;
evenements.push_back(Evenement{pos1, false, pos2, -1, -1});
}
for (int iRequete=0; iRequete<nbRequetes; iRequete++) {
const int iNoeud1 = getRacineAccessible(FORME_HUMAINE, villesDeparts[iRequete], seuilsBas[iRequete]);
const int iNoeud2 = getRacineAccessible(FORME_LOUP, villesArrivees[iRequete], seuilsHauts[iRequete]);
const int debut1 = arbres[FORME_HUMAINE][iNoeud1].debut;
const int fin1 = arbres[FORME_HUMAINE][iNoeud1].fin;
const int debut2 = arbres[FORME_LOUP][iNoeud2].debut;
const int fin2 = arbres[FORME_LOUP][iNoeud2].fin;
evenements.push_back(Evenement{debut1, true, debut2, fin2, iRequete});
evenements.push_back(Evenement{fin1, true, debut2, fin2, iRequete});
}
sort(evenements.begin(), evenements.end());
vector<int> nbAvants (nbRequetes);
fill(nbAvants.begin(), nbAvants.end(), -1);
for (const Evenement &evenement : evenements) {
if (evenement.estIntervalle) {
const int iRequete = evenement.iRequete;
if (nbAvants[iRequete] == -1) {
nbAvants[iRequete] = arbreBinaire.getSomme(evenement.debut, evenement.fin);
}
else {
nbAvants[iRequete] = arbreBinaire.getSomme(evenement.debut, evenement.fin) - nbAvants[iRequete];
}
}
else { // Mise à jour
arbreBinaire.incrementer(evenement.debut);
}
}
for (int iRequete=0; iRequete<nbRequetes; iRequete++) {
nbAvants[iRequete] = nbAvants[iRequete] > 0;
}
return nbAvants;
}
