// moreflags=grader.cpp
//
// 13
//
#include "train.h"
#include<vector>
#if not LOCAL
#define NDEBUG
#endif
#include<cassert>
#include<algorithm>
std::vector<std::vector<int>> add, reverse;
std::vector<int> order;
std::vector<char> state;
void work(int node){
assert(not state[node]); state[node]=true;
for(auto other: add[node]) if(not state[other])
work(other);
order.push_back(node);
}
std::vector<int> component;
void work2(int node){
assert(state[node]); state[node]=false;
for(auto other: reverse[node]) if(state[other])
work2(other);
component.push_back(node);
}
std::vector<int> awin;
std::vector<bool> keep;
std::vector<int> outDegree;
std::vector<int> a;
void remove(int node){
assert(keep[node]);
keep[node]=false;
for(auto other: reverse[node]) {
--outDegree[other];
assert(outDegree[other]>=0); assert(outDegree[other]<(int)add[other].size());
}
for(auto other: reverse[node]) if(keep[other]){
if(a[other]){
remove(other);
}else{
if(outDegree[other]==0)
remove(other);
}
}
}
void remove2(int node){
assert(keep[node]);
keep[node]=false;
for(auto other: reverse[node]) {
--outDegree[other];
assert(outDegree[other]>=0); assert(outDegree[other]<(int)add[other].size());
}
for(auto other: reverse[node]) if(keep[other]){
if(a[other]){
if(outDegree[other]==0)
remove2(other);
}else{
remove2(other);
}
}
}
std::vector<int> who_wins(std::vector<int> a_, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
::a=std::move(a_);
add.clear(); reverse.clear();
add.resize(a.size());
reverse.resize(a.size());
for(int index=0; index<(int)u.size(); ++index){
auto const first=u[index], sec=v[index];
add[first].push_back(sec); reverse[sec].push_back(first);
}
awin.assign(a.size(), true);
bool useful;
do{
useful=false;
/*
for(int mask=noChargeMask; mask; mask=(mask-1)&noChargeMask){
for(int node=0; node<(int)a.size(); ++node)
if(mask>>node&1){
if(a[node]){
if(not contains(mask|bwin, adjacent[node]))
goto next_mask;
}else{
if(((mask|bwin)&adjacent[node])==0)
goto next_mask;
}
}
bwin|=mask;
next_mask:;
}
for(int node=0; node<(int)a.size(); ++node)
if(a[node]){
if(contains(bwin, adjacent[node])) bwin|=1<<node;
}else{
if((bwin&adjacent[node])!=0) bwin|=1<<node;
}
*/
keep.assign(a.size(), true);
outDegree.resize(a.size());
for(int node=0; node<(int)a.size(); ++node){
outDegree[node]=(int)add[node].size();
}
for(int node=0; node<(int)add.size(); ++node)
if(keep[node] and r[node] and awin[node])
remove(node);
for(int node=0; node<(int)add.size(); ++node){
if(not awin[node]) assert(keep[node]);
if(awin[node] and keep[node]){
useful=true;
awin[node]=false;
}
}
// ======
keep.assign(a.size(), true);
outDegree.resize(a.size());
for(int node=0; node<(int)a.size(); ++node){
outDegree[node]=(int)add[node].size();
}
for(int node=0; node<(int)add.size(); ++node)
if(keep[node] and not awin[node])
remove2(node);
for(int node=0; node<(int)add.size(); ++node){
if(not awin[node]) assert(not keep[node]);
if(awin[node] and not keep[node]){
useful=true;
awin[node]=false;
}
}
}while(useful);
return std::move(awin);
}
