#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]; ll R[MAXN]; ll A[MAXN]; vector<pair<ll,ll>> pila; ll dfs(ll nd,ll lv){ if(vis[nd]){ ll j=lower_bound(ALL(pila),pair<ll,ll>{lvl[nd],(ll)0})-pila.begin(); ll cnt = pila.back().snd - (j-1>=0?pila[j-1].snd:0); return (cnt?1:0); } vis[nd]=true; lvl[nd]=lv; pila.pb({lv,R[nd]+(SZ(pila)>0?pila.back().snd:0)}); ll res = (A[nd]?0:1); for(auto i:adj[nd]){ if(A[nd]) res=max(res,dfs(i,lv+1)); else res=min(res,dfs(i,lv+1)); } //cout<<nd<<" "<<lv<<" "<<res<<'\n'; pila.pop_back(); return res; } 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]; } forn(i,0,SZ(a)) A[i]=a[i]; vector<int> res(SZ(r)); forn(i,0,SZ(r)){ mset(vis,false); pila.clear(); res[i]=dfs(i,0); } return res; }