#include "train.h"
#include <deque>
#include <vector>
using namespace std;
vector<int> who_wins(vector<int> estMax, vector<int> estRecharge,
vector<int> debs, vector<int> fins) {
int nbSommets = estMax.size();
vector<int> aggregs(nbSommets, 0);
vector<int> nbMins(nbSommets, 0);
vector<int> scores(nbSommets, 0);
vector<bool> estDans(nbSommets, true);
vector<vector<int>> fils(nbSommets);
vector<vector<int>> parents(nbSommets);
for(int iArc = 0;iArc < (int)debs.size();iArc++) {
fils[debs[iArc]].push_back(fins[iArc]);
parents[fins[iArc]].push_back(debs[iArc]);
}
int nbRecharges = 0;
deque<int> file;
for(int iSommet = 0;iSommet < nbSommets;iSommet++) {
file.push_back(iSommet);
if(estRecharge[iSommet])
nbRecharges += 1;
}
while(!file.empty()) {
int sommet = file.back();
file.pop_back();
if(scores[sommet] != nbRecharges + 1)
estDans[sommet] = false;
int oldScore = scores[sommet];
int score;
if(estMax[sommet]) {
score = 0;
for(int fil : fils[sommet]) {
score = max(score, scores[fil]);
}
}
else {
score = nbRecharges + 1;
int nb = 0;
for(int fil : fils[sommet]) {
if(scores[fil] < score) {
score = scores[fil];
nb = 0;
}
if(score == scores[fil]) {
nb++;
}
}
nbMins[sommet] = nb;
}
aggregs[sommet] = score;
if(estRecharge[sommet]) {
score += 1;
}
score = min(score, nbRecharges + 1);
scores[sommet] = score;
if(score == oldScore) continue;
for(int parent : parents[sommet]) {
if(estDans[parent]) continue;
if(estMax[parent] && score > aggregs[parent]) {
file.push_front(parent);
estDans[parent] = true;
}
if(!estMax[parent] && oldScore == aggregs[parent]) {
nbMins[parent]--;
if(nbMins[parent] == 0) {
file.push_front(parent);
estDans[parent] = true;
}
}
}
}
vector<int> estGagnant;
for(int iSommet = 0;iSommet < nbSommets;iSommet++) {
estGagnant.push_back(scores[iSommet] >= nbRecharges + 1);
}
return estGagnant;
}
