#include "train.h"
#include <iostream>
using namespace std;
const int MAX_NOEUD = 5e3;
const int MAX_ARC = 2e4;
int nbNoeud, nbArc;
bool estProprietaire[MAX_NOEUD];
bool estRechargeable[MAX_NOEUD];
bool dp[MAX_NOEUD];
vector<int> graphe[MAX_NOEUD];
vector<int> pile;
vector<int> result;
bool DFS(int curNoeud)
{
if(dp[curNoeud])
{
for(int i = (int)pile.size() - 1; i > -1; i--)
{
if(estRechargeable[pile[i]])
{
return true;
}
if(pile[i] == curNoeud)
{
return false;
}
}
}
dp[curNoeud] = true;
pile.push_back(curNoeud);
for(int voisin : graphe[curNoeud])
{
bool val = DFS(voisin);
if(!val && !estProprietaire[curNoeud])
{
return false;
}
if(val && estProprietaire[curNoeud])
{
return true;
}
}
pile.pop_back();
dp[curNoeud] = false;
if(graphe[curNoeud].size() == 0)
{
return false;
}
return !estProprietaire[curNoeud];
}
vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
nbNoeud = (int)a.size();
nbArc = (int)u.size();
for(int iNoeud = 0; iNoeud < nbNoeud; iNoeud++)
{
if(a[iNoeud] == 1)
{
estProprietaire[iNoeud] = true;
}
if(r[iNoeud])
{
estRechargeable[iNoeud] = true;
}
}
for(int iArc = 0; iArc < nbArc; iArc++)
{
graphe[u[iArc]].push_back(v[iArc]);
}
for(int iDep = 0; iDep < nbNoeud; iDep++)
{
if(DFS(iDep))
{
result.push_back(1);
}
else
{
result.push_back(0);
}
pile.clear();
for(int i = 0; i < nbNoeud; i++)
{
dp[i] = false;
}
}
return result;
}
