// moreflags=grader.cpp
// 8
#include "werewolf.h"
#include<vector>
#include<climits>
#include<algorithm>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>
struct FatDsu{
struct Node{
std::vector<int> children; // excluding itself
int root=-1;
};
std::vector<Node> data;
FatDsu(int number): data(number){}
int root(int node) const{
if(data[node].root>=0) node=data[node].root;
assert(data[node].root<0);
return node;
}
bool join(int first, int sec){
first=root(first); sec=root(sec);
if(first==sec) return false;
if(data[first].children.size()<data[sec].children.size()) std::swap(first, sec);
for(auto it: data[sec].children){
assert(data[it].root==sec);
assert(data[it].children.empty());
data[it].root=first;
data[first].children.push_back(it);
}
data[sec].root=first;
data[sec].children.clear();
data[first].children.push_back(sec);
return true;
}
};
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) {
std::vector<std::vector<int>> add(N);
for(int index=0; index<(int)X.size(); ++index){
add[X[index]].push_back(Y[index]);
add[Y[index]].push_back(X[index]);
}
struct T{int s, e, l, r, index;
std::vector<int> erComponent;
};
std::vector<T> queries(S.size());
for(int index=0; index<(int)queries.size(); ++index)
queries[index]={S[index], E[index], L[index], R[index], index};
std::vector<int> result(S.size());
{
std::sort(begin(queries), end(queries), [&](auto const& first, auto const& sec){
return first.r<sec.r;
});
FatDsu tree(N);
auto iterator=queries.begin();
for(int index=0; iterator!=queries.end(); ++index){
for(auto other: add[index]) if(other<=index)
tree.join(index, other);
while(iterator!=queries.end() and iterator->r==index){
iterator->erComponent=tree.data[tree.root(iterator->e)].children;
++iterator;
}
}
}
{
std::sort(begin(queries), end(queries), [&](auto const& first, auto const& sec){
return first.l>sec.l;
});
FatDsu tree(N);
auto iterator=queries.begin();
for(int index=N-1; iterator!=queries.end(); --index){
for(auto other: add[index]) if(other>=index)
tree.join(index, other);
while(iterator!=queries.end() and iterator->l==index){
auto const curRoot=tree.root(iterator->s);
for(auto it: iterator->erComponent) if(tree.root(it)==curRoot){
result[iterator->index]=1;
break;
}
result[iterator->index]=result[iterator->index] or (tree.root(iterator->e)==curRoot);
++iterator;
}
}
}
return result;
/*
if((int)X.size()==N-1){
std::vector<int> order; order.reserve(N);
{
auto const index=int(std::find_if(begin(add), end(add), [&](auto const& it){return it.size()==1;})-add.begin());
order.push_back(index);
assert(add[index].size()==1); order.push_back(add[index][0]);
}
while((int)order.size()!=N){
if(add[order.back()].size()!=2) return {};
for(auto it: add[order.back()]) if(it!=order.end()[-2]){
order.push_back(it);
break;
}
}
std::vector<int> pos(N);
for(int index=0; index<(int)order.size(); ++index)
pos[order[index]]=index;
}
*/
}
