#include <iostream>
#include <cstdio>
#include <vector>
#include "train.h"
using namespace std;
const int MAX_NOEUDS = (5000);
vector <int> Remonte[MAX_NOEUDS];
bool DP[MAX_NOEUDS];
bool Arezou[MAX_NOEUDS];
bool Charge[MAX_NOEUDS];
bool Calc[MAX_NOEUDS];
bool Pris[MAX_NOEUDS];
int Deg[MAX_NOEUDS];
int File[MAX_NOEUDS];
int deb = 0, fin = 0;
int nbNoeuds, nbAretes;
void Reset() {
deb = 0, fin = 0;
for (int i = 0; i < nbNoeuds; i ++)
{
Calc[i] = false;
Pris[i] = false;
Deg[i] = 0;
}
for (int i = 0; i < nbNoeuds; i ++)
{
for (int dest : Remonte[i])
Deg[dest] ++;
}
return;
}
void Add(int noeud) {
if (Calc[noeud])
return;
Calc[noeud] = true;
for (int dest : Remonte[noeud])
{
if (!Pris[dest] && (Arezou[dest] || -- Deg[dest] == 0))
{
File[fin ++] = dest;
Pris[dest] = true;
}
}
return;
}
bool Bfs(bool first) {
for (int i = 0; i < nbNoeuds; i ++)
{
if (DP[i] && Charge[i])
Add(i);
}
while (deb < fin)
{
Add(File[deb ++]);
}
if (first)
{
for (int i = 0; i < nbNoeuds; i ++)
{
DP[i] = Pris[i];
}
return false;
}
bool isOver = true;
for (int i = 0; i < nbNoeuds; i ++)
{
if (DP[i] && !Pris[i])
{
DP[i] = false;
isOver = false;
}
}
return isOver;
}
vector<int> who_wins(vector<int> Proprio, vector<int> Energie, vector<int> Left, vector<int> Right) {
nbNoeuds = Proprio.size();
nbAretes = Left.size();
for (int i = 0; i < nbNoeuds; i ++)
{
Arezou[i] = Proprio[i];
Charge[i] = Energie[i];
if (Charge[i])
DP[i] = true;
}
for (int i = 0; i < nbAretes; i ++)
{
Remonte[Right[i]].push_back(Left[i]);
}
Reset();
Bfs(true);
Reset();
while (!Bfs(false))
Reset();
vector <int> Ans;
for (int i = 0; i < nbNoeuds; i ++)
{
Ans.push_back(DP[i]);
}
return Ans;
}
