#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int MAX_SOM=200*1000+5,MAX_REQ=200*1000+5;
int nbSom,nbAre,nbReq,numEuler;
int pere[MAX_SOM];
vector<int> adjaGrand[MAX_SOM],adjaPetit[MAX_SOM];
vector<pair<int,int>> reqHom[MAX_SOM],reqLoup[MAX_SOM];
int numHom[MAX_REQ],numLoup[MAX_REQ];
vector<int> rep;
int pereHom[MAX_SOM],pereLoup[MAX_SOM];
vector<int> filsHom[MAX_SOM],filsLoup[MAX_SOM];
int eulerHomme[MAX_SOM][2],eulerLoup[MAX_SOM][2];
int idSom[MAX_SOM];
vector<tuple<int,int,int>> quest[MAX_SOM];
vector<int> enCours;
int dessus[MAX_SOM],somTot[MAX_SOM];
int diff[MAX_SOM];
int find(int pos) {
if (pos!=pere[pos]) {
pere[pos]=find(pere[pos]);
}
return pere[pos];
}
void DFS_homme(int pos) {
numEuler++;
idSom[numEuler]=pos;
eulerHomme[pos][0]=numEuler;
for (int i:filsHom[pos]) {
DFS_homme(i);
}
eulerHomme[pos][1]=numEuler;
}
void DFS_loup(int pos) {
numEuler++;
eulerLoup[pos][0]=numEuler;
for (int i:filsLoup[pos]) {
DFS_loup(i);
}
eulerLoup[pos][1]=numEuler;
}
bool inclusLoup(int petit,int grand) {
return (eulerLoup[grand][0]<=eulerLoup[petit][0] and eulerLoup[grand][1]>=eulerLoup[petit][1]);
}
void remonte(int pos) {
somTot[pos]=dessus[pos];
for (int i:filsLoup[pos]) {
remonte(i);
somTot[pos]+=somTot[i];
}
}
int calc(int pos) {
int ans=somTot[pos];
for (int i:enCours) {
if (inclusLoup(i,pos)) {
ans++;
}
}
return ans;
}
vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L,vector<int> R) {
nbSom=N;
nbAre=X.size();
nbReq=S.size();
int debAre,finAre;
for (int i=0;i<nbAre;i++) {
debAre=min(X[i],Y[i]);
finAre=max(X[i],Y[i]);
adjaGrand[debAre].push_back(finAre);
adjaPetit[finAre].push_back(debAre);
}
for (int i=0;i<nbReq;i++) {
reqHom[L[i]].push_back({S[i],i});
reqLoup[R[i]].push_back({E[i],i});
}
for (int i=0;i<nbSom;i++) {
pere[i]=i;
}
for (int i=nbSom-1;i>=0;i--) {
for (int j:adjaGrand[i]) {
if (find(j)!=i) {
pereHom[find(j)]=i;
filsHom[i].push_back(find(j));
pere[find(j)]=i;
}
}
for (auto j:reqHom[i]) {
numHom[j.second]=find(j.first);
}
}
for (int i=0;i<nbSom;i++) {
pere[i]=i;
}
for (int i=0;i<nbSom;i++) {
for (int j:adjaPetit[i]) {
if (find(j)!=i) {
pereLoup[find(j)]=i;
filsLoup[i].push_back(find(j));
pere[find(j)]=i;
}
}
for (auto j:reqLoup[i]) {
numLoup[j.second]=find(j.first);
}
}
/*for (int i=0;i<nbReq;i++) {
cout<<numHom[i]<<" "<<numLoup[i]<<endl;
}*/
numEuler=-1;
DFS_homme(0);
DFS_loup(nbSom-1);
/*for (int i=0;i<nbSom;i++) {
cout<<i<<" : ";
for (int j:filsHom[i]) {
cout<<j<<" ";
}
cout<<endl;
}
for (int i=0;i<nbSom;i++) {
cout<<i<<" : ";
for (int j:filsLoup[i]) {
cout<<j<<" ";
}
cout<<endl;
}
for (int i=0;i<nbSom;i++) {
cout<<i<<" : "<<eulerLoup[i][0]<<" "<<eulerLoup[i][1]<<endl;
}*/
for (int i=0;i<nbReq;i++) {
if (eulerHomme[numHom[i]][0]>0) {
quest[eulerHomme[numHom[i]][0]-1].push_back(make_tuple(numLoup[i],i,-1)); ////à voir
}
quest[eulerHomme[numHom[i]][1]].push_back(make_tuple(numLoup[i],i,1)); ////à voir
}
for (int i=0;i<nbSom;i++) {
if(i%(int)sqrt(nbSom)==0) {
for (int j:enCours) {
dessus[j]++;
}
enCours.clear();
remonte(nbSom-1);
}
enCours.push_back(idSom[i]);
for (auto j:quest[i]) {
diff[get<1>(j)]+=calc(get<0>(j))*get<2>(j);
}
}
for (int i=0;i<nbReq;i++) {
if (diff[i]<=0) {
rep.push_back(0);
}
else {
rep.push_back(1);
}
}
return rep;
}
