#include "train.h"
#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<vector<int>> adjlist;
vector<vector<int>> revadjlist;
vector<bool> status;
vector<int> cp;
bool dfs(int node, int ret){
//cout<<"dfs "<<node<<' '<<ret<<endl;
if (node-n==ret){
return true;
}
status[node]=true;
bool hascharged = node>=n;
if (cp[node-(hascharged*n)]&&(!hascharged)){
node+=n;
hascharged=true;
}
int nd = node-(hascharged*n);
for (int i : adjlist[nd]){
if (status[i+(hascharged*n)]){
continue;
}
if (dfs(i+(hascharged*n),ret)){
return true;
}
}
return false;
}
vector<int> aall(vector<int> &charging, vector<int> &u, vector<int> &v){
adjlist.resize(n);
revadjlist.resize(n);
for (int i = 0; i<m; i++){
adjlist[u[i]].push_back(v[i]);
revadjlist[v[i]].push_back(u[i]);
}
//cout<<"bleh"<<endl;
cp=charging;
vector<int> use;
for (int i = 0; i<n; i++){
// is there cycle from this node involving a charging point?
status.assign(2*n,false);
if (dfs(i,i)){
use.push_back(i);
}
}
//cout<<"bleh"<<endl;
vector<int> visited(n,0);
queue<int> q;
for (int i : use){
visited[i]=1;
q.push(i);
}
while (q.size()>0){
int f = q.front();
q.pop();
for (int i : revadjlist[f]){
if (!visited[i]){
visited[i]=1;
q.push(i);
}
}
}
return visited;
}
vector<int> ball(vector<int> &charging, vector<int> &u, vector<int> &v){
return vector<int>();
}
std::vector<int> who_wins(std::vector<int> aowns, std::vector<int> charging, std::vector<int> u, std::vector<int> v) {
n=aowns.size();
m=u.size();
int numa = 0;
for (int i : aowns){
numa+=i;
}
if (numa==n){
return aall(charging,u,v);
}
/*if (numa==0){
return ball(charging,u,v);
}*/
vector<bool> iscycle(n);
vector<bool> edgetonext(n,false);
for (int i = 0; i<m; i++){
if (u[i]==v[i]){
iscycle[u[i]]=true;
} else {
edgetonext[u[i]]=true;
}
}
vector<int> ans(n);
for (int i = n-1; i>=0; i--){
if (iscycle[i]){
if (aowns[i]&&charging[i]){
ans[i]=1;
} else if ((!aowns[i])&&(!charging[i])){
ans[i]=0;
} else {
if (!edgetonext[i]){
if (charging[i]){
ans[i]=1;
} else {
ans[i]=0;
}
} else {
ans[i]=ans[i+1];
}
}
} else {
ans[i]=ans[i+1];
}
}
return ans;
}
