#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 CurNodes[MAX_NOEUDS];
int sz = 0;
int Copy[MAX_NOEUDS];
int szCopy = 0;
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 = 0; i < sz; i ++)
{
int id = CurNodes[i];
Calc[id] = false;
Pris[id] = false;
Deg[id] = DegI[id];
}
return;
}
void Add(int noeud) {
if (Calc[noeud])
return;
Calc[noeud] = true;
int _sz = Remonte[noeud].size();
for (int i = 0; i < _sz; i ++)
{
int dest = Remonte[noeud][i];
if (!Pris[dest] && (Arezou[dest] || -- Deg[dest] == 0))
{
File[fin ++] = dest;
Pris[dest] = true;
}
}
return;
}
bool Bfs() {
for (int i = 0; i < sz; i ++)
{
int id = CurNodes[i];
if (DP[id] && Charge[id])
Add(id);
}
while (deb < fin)
{
Add(File[deb ++]);
}
bool isOver = true;
szCopy = 0;
for (int i = 0; i < sz; i ++)
{
int id = CurNodes[i];
if (DP[id] && !Pris[id])
{
DP[id] = false;
isOver = false;
Pris[id] = true;
}
else
Copy[szCopy ++] = id;
}
for (int i = 0; i < szCopy; i ++)
{
CurNodes[i] = Copy[i];
}
sz = szCopy;
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[sz ++] = i;
}
for (int i = 0; i < nbAretes; i ++)
{
Remonte[Right[i]].push_back(Left[i]);
DegI[Left[i]] ++;
}
Reset();
while (!Bfs())
Reset();
vector <int> Ans;
for (int i = 0; i < nbNoeuds; i ++)
{
Ans.push_back(DP[i]);
}
return Ans;
}
