#include "train.h"
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int maxN = 5000;
vector<int> nei[maxN];
int charge[maxN], a[maxN];
int ans[maxN];
int col[maxN], isCyc[maxN];
int n;
vector<int> rnei[maxN];
bool used1[maxN];
void DFS1(int v, vector<int>& sorted)
{
used1[v] = true;
for (int to: nei[v])
if (!used1[to])
DFS1(to, sorted);
sorted.push_back(v);
}
void DFS2(int v, int curcol)
{
col[v] = curcol;
for (int to: rnei[v])
if (!col[to])
{
DFS2(to, curcol);
isCyc[curcol] = true;
}
else if (col[to] == curcol)
isCyc[curcol] = true;
}
void SCC()
{
vector<int> sorted;
for (int i = 0; i < n; ++i)
if (!used1[i])
DFS1(i, sorted);
reverse(sorted.begin(), sorted.end());
int cols = 0;
for (int v: sorted)
if (!col[v])
DFS2(v, ++cols);
}
bool used3[maxN];
void DFS3(int v)
{
used3[v] = true;
ans[v] = 1;
for (int to: rnei[v])
if (!used3[to])
DFS3(to);
}
vector<int> Solve3()
{
SCC();
vector<bool> goodcol(n);
for (int v = 0; v < n; ++v)
if (charge[v])
goodcol[col[v]] = true;
for (int v = 0; v < n; ++v)
if (goodcol[col[v]] && isCyc[col[v]] && !used3[v])
DFS3(v);
return vector<int>(ans, ans + n);
}
bool used4[maxN];
int DFS4(int v)
{
static set<int> cur;
cur.insert(v);
used4[v] = true;
for (int to: nei[v])
if (!used4[to] && !charge[to])
isCyc[v] = max(isCyc[v], DFS4(to));
else if (cur.count(to))
isCyc[v] = 1;
cur.erase(v);
return isCyc[v];
}
vector<int> Solve4()
{
for (int v = 0; v < n; ++v)
if (!used3[v] && !charge[v])
DFS4(v);
for (int v = 0; v < n; ++v)
if (!used3[v] && isCyc[v])
DFS3(v);
for (int v = 0; v < n; ++v)
ans[v] = (ans[v] ? 0 : 1);
return vector<int>(ans, ans + n);
}
vector<int> Solve1()
{
vector<bool> loop(n), isend(n, true);
for (int v = 0; v < n; ++v)
{
for (int to: nei[v])
if (v == to)
loop[v] = true;
else
isend[v] = false;
loop[v] = max(loop[v], isend[v]);
}
for (int i = 0, st = 0; i < n; ++i)
{
if (loop[i] && charge[i] && a[i] || isend[i] && charge[i])
{
for (int j = st; j <= i; ++j)
ans[j] = 1;
st = i + 1;
}
else if (loop[i] && !charge[i] && !a[i] || isend[i] && !charge[i])
{
for (int j = st; j <= i; ++j)
ans[j] = 0;
st = i + 1;
}
}
return vector<int>(ans, ans + n);
}
bool OK(int mask)
{
vector<int> cycle;
for (int i = 0; i < n; ++i)
if (mask & (1 << i))
{
if (charge[i])
return false;
else
cycle.push_back(i);
}
for (int u: cycle)
{
bool g = false;
if (a[u])
{
g = true;
for (int to: nei[u])
if (!count(cycle.begin(), cycle.end(), to) && ans[to] != 0)
g = false;
}
else
{
g = false;
for (int to: nei[u])
if (count(cycle.begin(), cycle.end(), to) || ans[to] == 0)
g = true;
}
if (!g) return false;
}
return true;
}
vector<int> Solve2()
{
for (int i = 0; i < n; ++i)
ans[i] = 1;
for (int tch = 0; tch < 4 * n; ++tch)
{
for (int mask = 1; mask < (1 << n); ++mask)
{
if (OK(mask))
for (int i = 0; i < n; ++i)
if (mask & (1 << i))
ans[i] = 0;
}
for (int i = 0; i < n; ++i)
for (int u = 0; u < n; ++u)
{
bool g = false;
if (a[u])
{
g = true;
for (int to: nei[u])
if (ans[to] != 0)
g = false;
}
else
{
g = false;
for (int to: nei[u])
if (ans[to] == 0)
g = true;
}
if (g)
ans[u] = 0;
}
}
return vector<int>(ans, ans + n);
}
std::vector<int> who_wins(std::vector<int> a_, std::vector<int> charge_, std::vector<int> u, std::vector<int> v) {
n = a_.size();
for (int i = 0; i < n; ++i)
a[i] = a_[i], charge[i] = charge_[i];
for (int i = 0; i < u.size(); ++i)
nei[u[i]].push_back(v[i]);
for (int v = 0; v < n; ++v)
for (int to: nei[v])
rnei[to].push_back(v);
if (n <= 15)
return Solve2();
if (!count(a, a + n, 0))
return Solve3();
if (!count(a, a + n, 1))
return Solve4();
return Solve1();
}
