#include "train.h" #include <bits/stdc++.h> #define fst first #define snd second #define pb push_back #define SZ(x) (int)x.size() #define ALL(x) x.begin(),x.end() #define forn(i,a,b) for(int i = a; i<b;i++) #define mset(a,v) memset(a,v,sizeof(a)) using namespace std; typedef long long ll; const int MAXN = 5000+5; vector<ll> adj[MAXN]; ll lvl[MAXN]; bool vis[MAXN]; bool good[MAXN]; ll R[MAXN]; vector<pair<ll,ll>> pila; bool yes=true; void dfs(ll nd,ll ini,ll cnt){ if(vis[nd] && nd==ini && cnt==0){ yes=true; } if(vis[nd]) return; vis[nd]=true; for(auto i:adj[nd]) if(!R[i]){ dfs(i,ini,cnt); } } void ndfs(ll nd, ll p){ vis[nd]=true; if(good[nd]) yes=true; if(yes) return; for(auto i:adj[nd]) if(i!=p && !vis[i]){ ndfs(i,nd); if(yes) return; } } std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) { forn(i,0,SZ(u)){ adj[u[i]].pb(v[i]); } forn(i,0,SZ(r)){ R[i]=r[i]; } mset(good,-1); forn(i,0,SZ(r)) if(!r[i]){ mset(vis,false); yes=false; dfs(i,i,0); if(yes) good[i]=1; } vector<int> res(SZ(r),0); forn(i,0,SZ(r))if(!good[i]){ mset(vis,false); yes=false; ndfs(i,-1); if(yes) res[i]=0; else res[i]=1; } return res; }