#include "train.h"
#include <bits/stdc++.h>
using namespace std;
using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
#define sz(x) (int((x).size()))
int n, m;
vi charging, owner, scc;
vvi G, R;
// node, which owner, allowing charging stations
void dfs1(int u, int o, int t, vi &order, vi &cmp, vvi &G) {
for (auto v : G[u]) {
if (cmp[v] != -1) continue;
if (owner[v] != o) continue;
if (charging[v] && !t) continue;
cmp[v] = cmp[u];
dfs1(v, o, t, order, cmp, G);
}
order.push_back(u);
}
vi who_wins(vi a, vi r, vi u, vi v) {
n = sz(a), m = sz(u);
charging = r; owner = a;
G.assign(n, vi()); R.assign(n, vi());
for (int i = 0; i < m; i++) {
G[u[i]].push_back(v[i]), R[v[i]].push_back(u[i]);
}
n = sz(a), m = sz(u);
scc.assign(n, -1);
int timer = 0;
vi cmp1(n, -1), order1, order2, sown(n, 0);
for (int i = 0; i < n; i++) {
if (cmp1[i] != -1) continue;
cmp1[i] = timer++; dfs1(i, owner[i], owner[i] == 0 ? 0 : 1, order1, cmp1, G);
}
timer = 0;
reverse(all(order1));
for (auto i : order1) {
if (scc[i] != -1) continue;
scc[i] = timer++; dfs1(i, owner[i], owner[i] == 0 ? 0 : 1, order2, scc, R);
sown[scc[i]] = owner[i];
}
vi has_charger(n, 0);
vvi S(n, vi()), B(n, vi()), mems(n, vi()); vi deg(n, 0), len(n, 0);
set<pi> seen;
for (int i = 0; i < n; i++) {
if (scc[i] == -1) continue;
if (sown[scc[i]] != 0) has_charger[scc[i]] |= charging[i];
len[scc[i]]++; mems[scc[i]].push_back(i);
for (auto v : G[i]) {
if (scc[i] == scc[v]) continue;
if (scc[v] == -1) continue;
if (sown[i] != sown[v]) continue;
if (seen.count({scc[i], scc[v]})) continue;
seen.insert({scc[i], scc[v]});
S[scc[i]].push_back(scc[v]);
B[scc[v]].push_back(scc[i]);
deg[scc[v]]++;
}
}
for (int i = 0; i < n; i++) {
if (len[i] != 1 || sown[i] != 0) continue;
has_charger[i] = true;
int u = mems[i][0];
for (auto v : G[u]) has_charger[i] = has_charger[i] || u == v;
}
for (int i = 0; i < n; i++) {
if (!has_charger[i] || len[i] != 1 || sown[i] == 0) continue;
bool selfloop = false; int u = mems[i][0];
for (auto v : G[u]) selfloop = selfloop || u == v;
has_charger[i] = has_charger[i] && selfloop;
}
queue<int> q; for (int i = 0; i < n; i++) if (deg[i] == 0 && len[i] > 0) q.push(i);
vector<int> order;
while (!q.empty()) {
int u = q.front(); q.pop();
order.push_back(u);
for (auto v : S[u]) {
if (--deg[v] == 0) q.push(v);
}
}
reverse(all(order));
for (auto u : order) {
for (auto v : S[u]) {
if (sown[u] != 0) has_charger[u] |= has_charger[v];
else has_charger[u] = has_charger[u] && has_charger[v];
}
}
vi res(n, 0);
for (int i = 0; i < n; i++) if (scc[i] != -1 && has_charger[scc[i]]) res[i] = 1;
return res;
}
