// moreflags=grader.cpp
#include "werewolf.h"
#include<vector>
#include<set>
#include<climits>
#include<algorithm>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>
struct Dsu{ // with path compression but without union by rank
std::vector<int> data; // positive: parent, negative: ~(minimum in component)
Dsu(int number): data(number){
for(int node=0; node<number; ++node)
data[node]=~ node;
}
int root(int node){return data[node]>=0 ? data[node]=root(data[node]): node;}
int minimumInComponent(int node){
return ~data[root(node)];
}
bool join(int first, int sec){
first=root(first); sec=root(sec);
if(first==sec) return false;
data[first]=std::max(data[first], data[sec]); // inverted
data[sec]=first;
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>> greaterAdd(N), lessAdd(N);
for(int index=0; index<(int)X.size(); ++index){
auto const [a, b]=std::minmax({X[index], Y[index]});
assert(a!=b);
greaterAdd[a].push_back(b);
lessAdd[N-1-b].push_back(N-1-a);
}
auto const process=[&](std::vector<std::vector<int>>& add)->std::vector<int>{
// add: adjacency list (elements of list [i] must be strictly greater than i)
// also reuse add for the children of the resulting par
// (node n is for -1)
std::vector<int> par(add.size(), -1);
Dsu dsu((int)add.size());
for(auto index=(int)add.size(); index--;){
for(auto other: add[index]){
other=dsu.minimumInComponent(other);
if(other>index){
auto const success=dsu.join(index, other);
assert(success);
assert(par[other]==-1);
par[other]=index;
}else assert(other==index);
}
}
for(auto& it: add) it.clear();
add.emplace_back();
for(int node=0; node<(int)par.size(); ++node){
(par[node]<0 ? add.back(): add[par[node]]).push_back(node);
}
return par;
};
std::vector<int> greaterPar=process(greaterAdd);
std::vector<int> lessPar=process(lessAdd);
// greaterPar: the equivalent structure of traversing with the additional condition (vertex >= L)
// for some L
// ( i -> greaterPar[i] ) where greaterPar[i]<i
// lessPar: vice versa, but with flipped vertex indices
struct Jump{
std::vector<std::vector<int>> data;
// assumes -1 is the virtual root
Jump(std::vector<int> value): data{std::move(value)}{
for(int step=1; step<(int)data.back().size(); step<<=1){
std::vector<int> const& a=data.back();
auto b=a;
bool useful=false;
for(auto& it: b) if(it>=0){
it=a[it];
if(it>=0) useful=true;
}
if(useful)
data.push_back(std::move(b));
else break;
}
}
int get(int node, int least)const{
// assumes par[node]<node for all node, find minimum ancestor >=least
for(auto layer=data.size(); layer--;)
if(data[layer][node]>=least) node=data[layer][node];
return node;
}
};
Jump greaterJump(std::move(greaterPar)), lessJump(std::move(lessPar));
struct Query{int node, index;};
std::vector<std::vector<Query>> queries(N);
// [node1] = (node2, query): query with index==query -> greater subtree rooted at node1
// has any common vertex with less subtree rooted at node2?
for(int query=0; query<(int)S.size(); ++query){
int node1=greaterJump.get(S[query], L[query]);
int node2=lessJump.get(N-1-E[query], N-1-R[query]);
queries[node1].push_back({node2, query});
}
std::vector<int> result(S.size());
// solve all queries
/* // * not necessary
auto const subtreeSize=[&]{ // of greater
std::vector<int> result(N);
auto const work=[&](auto work, int node)->int{
auto cur=1;
for(auto other: greaterAdd[node])
cur+=work(work, other);
return result[node]=cur;
};
for(auto it: greaterAdd[N]) work(work, it);
for(auto it: result) assert(it>0);
return result;
}();
*/
auto const merge=[&](std::set<int> first, std::set<int> sec){
if(first.size()<sec.size()) std::swap(first, sec);
for(auto it: sec){
auto const success=first.insert(it).second;
assert(success);
}
return first;
};
std::vector<int> lessFirst(N), lessLast(N); // first and last index in preorder traversal of the less tree
{ // construct ^
int cur=0;
auto const work=[&](auto work, int node)->void{
assert(lessFirst[node]==0);
lessFirst[node]=cur++;
for(auto other: lessAdd[node])
work(work, other);
lessLast[node]=cur;
};
for(auto node: lessAdd[N]){
work(work, node);
}
assert(cur==N);
}
// wait it's not necessary to compute subtreeSize if std::set is used anyway
auto const work=[&](auto work, int node)->std::set<int>{
std::set<int> curSet{lessFirst[N-1-node]};
for(auto other: greaterAdd[node])
curSet=merge(std::move(curSet), work(work, other));
for(auto [node2, queryIndex]: queries[node]){
auto const iterator=curSet.lower_bound(lessFirst[node2]);
if(iterator!=curSet.end() and *iterator<lessLast[node2])
result[queryIndex]=1;
}
return curSet;
};
for(auto it: greaterAdd[N]) work(work, it);
return result;
}
