#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];
vector <int> CurNodes;
int DegI[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 : CurNodes)
{
Calc[i] = false;
Pris[i] = false;
Deg[i] = DegI[i];
}
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 rebuild) {
for (int i : CurNodes)
{
if (DP[i] && Charge[i])
Add(i);
}
while (deb < fin)
{
Add(File[deb ++]);
}
bool isOver = true;
vector <int> nv;
for (int i : CurNodes)
{
if (DP[i] && !Pris[i])
{
DP[i] = false;
isOver = false;
Pris[i] = true;
}
else
nv.push_back(i);
}
CurNodes = nv;
if (rebuild)
{
for (int i : CurNodes)
{
nv.clear();
for (int dest : Remonte[i])
if (DP[dest])
nv.push_back(dest);
Remonte[i] = nv;
}
}
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];
DP[i] = true;
CurNodes.push_back(i);
}
for (int i = 0; i < nbAretes; i ++)
{
Remonte[Right[i]].push_back(Left[i]);
DegI[Left[i]] ++;
}
int cnt = 0;
Reset();
while (!Bfs((++ cnt) % 100))
Reset();
vector <int> Ans;
for (int i = 0; i < nbNoeuds; i ++)
{
Ans.push_back(DP[i]);
}
return Ans;
}
