#include "train.h"
#include <stdlib.h>
using namespace std;
const int N = 5000;
typedef vector<int> vi;
int *ej[N], eo[N], dd[N][N + 1], out[N], qu[N * (N + 1)], n; char rr[N];
vi who_wins(vi aa, vi rr_, vi uu, vi vv) {
int m = uu.size(), h, i, j, t, t_, cnt;
vi ans(n = aa.size());
for (i = 0; i < n; i++)
rr[i] = rr_[i];
for (h = 0; h < m; h++)
out[uu[h]]++, eo[vv[h]]++;
for (i = 0; i < n; i++)
ej[i] = (int *) malloc(eo[i] * sizeof *ej[i]), eo[i] = 0;
for (h = 0; h < m; h++)
ej[vv[h]][eo[vv[h]]++] = uu[h];
for (i = 0; i < n; i++) {
dd[i][0] = !rr[i] ? 1 : 0;
for (t = 1; t <= n; t++)
dd[i][t] = t == n || !rr[i] ? (aa[i] ? out[i] : 1) : 0;
}
cnt = 0;
for (i = 0; i < n; i++)
if (--dd[i][0] == 0)
qu[cnt++] = i * (n + 1) + 0;
while (cnt) {
int it = qu[--cnt], o;
i = it / (n + 1), t = it % (n + 1);
dd[i][t] = -1;
for (o = eo[i]; o--; ) {
j = ej[i][o];
if (t != n) {
if (--dd[j][t + 1] == 0)
qu[cnt++] = j * (n + 1) + t + 1;
} else if (rr[i])
for (t_ = 1; t_ <= n; t_++)
if (--dd[j][t_] == 0)
qu[cnt++] = j * (n + 1) + t_;
}
}
for (i = 0; i < n; i++)
ans[i] = dd[i][n] >= 0;
return ans;
}
