// moreflags=grader.cpp
//
// 13
// subtask (all owned by A)
//
#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;
void work3(int node){
assert(not state[node]); state[node]=true;
for(auto other: reverse[node]) if(not state[other])
work3(other);
awin[node]=true;
}
std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
if(not std::all_of(begin(a), end(a),[&](char it){return it;})) return {};
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);
}
order.clear(); order.reserve(a.size());
state.assign(a.size(), false);
for(int node=0; node<(int)a.size(); ++node)
if(not state[node])
work(node);
assert(order.size()==a.size());
assert(std::all_of(begin(state), end(state),[&](char it){return it;}));
awin.assign(a.size(), false);
std::for_each(order.rbegin(), order.rend(),[&](int node){
if(state[node]){
component.clear();
work2(node);
bool const okay=(component.size()>1 or std::find(begin(add[component[0]]), end(add[component[0]]), component[0])!=add[component[0]].end()
) and std::any_of(begin(component), end(component),
[&](int it){return r[it];});
if(okay)
for(auto it: component) awin[it]=true;
}
});
assert(std::all_of(begin(state), end(state),[&](char it){return not it;}));
for(int node=0; node<(int)a.size(); ++node)
if(awin[node] and not state[node])
work3(node);
return std::move(awin);
}
