// moreflags=grader.cpp
// upsolve
// if I can't can't solve it in 5 hours, it's the same as if I can't solve it at all.
// As expected of an IOI problem, the implementation is not hard.
#include "werewolf.h"
#include<vector>
#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
std::vector<int> result(S.size());
for(int query=0; query<(int)S.size(); ++query){
int node1=S[query];
while(greaterPar[node1]>=L[query]) node1=greaterPar[node1];
int node2=N-1-E[query];
while(lessPar[node2]>=N-1-R[query]) node2=lessPar[node2];
// call handle on all children of node in preorder
auto iterate=[&](auto iterate, int node, std::vector<std::vector<int>> const& add, auto handle)->void{
handle(node);
for(auto other: add[node])
iterate(iterate, other, add, handle);
};
std::vector<char> mark(N);
iterate(iterate, node1, greaterAdd, [&](int node){ mark[node]=true; });
bool okay=false;
iterate(iterate, node2, lessAdd, [&](int node){ okay=okay or mark[N-1-node]; });
result[query]=okay;
}
return result;
}
