#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]; vector<pair<ll,ll>> pila; ll dfs(ll nd,ll lv){ if(vis[nd]){ ll j=SZ(pila)-1; ll cnt = 0; while(j>=0 && pila[j].snd!=nd){ j--; cnt+=R[pila[j].snd]; } cnt+=R[nd]; return (cnt?1:0); } vis[nd]=true; lvl[nd]=lv; pila.pb({lv,nd}); ll res = 0; for(auto i:adj[nd]){ res=max(res,dfs(i,lv+1)); } 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]; } vector<int> res(SZ(r)); forn(i,0,SZ(r)){ mset(vis,false); pila.clear(); res[i]=dfs(i,0); } return res; }