Submission #299634

#TimeUsernameProblemLanguageResultExecution timeMemory
299634REALITYNBToy Train (IOI17_train)C++14
0 / 100
1303 ms1784 KiB
#include <bits/stdc++.h> using namespace std; vector<int> adj[5001] , vis(5001); bool cycle = 0 , tar ; void dfs(int a ){ vis[a]=1 ; for(int& x : adj[a]){ if(vis[x]) cycle=1 ; if(vis[x]) continue ; dfs(x) ; } } void dfss(int a ){ vis[a] =1 ; for(int& x :adj[a]){ if(vis[x]&&tar==x) cycle= 1 ; if(vis[x]) continue ; dfss(x) ; } } vector<int> is(5001) ; vector<int> radj[5001] ; bool res = 0 ; void propa(int a , int c , vector<int>& viss){ viss[a]=1 ; res|=is[a] ; for(int&x : radj[a]){ if(viss[x]) continue ; propa(x,c,viss) ; } } vector<int> who_wins(vector<int> a , vector<int> c , vector<int> u , vector<int> v){ int n = a.size() ; int m = u.size() ; int ar = a[0] ; for(int i=0;i<m;i++) radj[u[i]].push_back(v[i]) ; if(ar){ //arzou case for(int i=0;i<m;i++){ adj[u[i]].push_back(v[i]) ; } for(int i=0;i<n;i++){ if(c[i]==0) continue ; for(int& x : vis) x = 0 ; cycle = 0 ; tar= i ; dfss(i) ; is[i] = cycle ; } } else{ //berzou case for(int i=0;i<m;i++){ if(c[u[i]]) continue ; if(c[v[i]]) continue ; adj[u[i]].push_back(v[i]) ; } for(int i=0;i<n;i++){ if(vis[i]) continue ; cycle = 0 ; dfs(i) ; is[i]= cycle ; } } vector<int> ans(n) ; for(int i=0;i<n;i++){ vector<int> v(5001) ; res= 0 ; propa(i,0,v) ; ans[i]= res ; } ar^=1 ; for(int i=0;i<n;i++) ans[i]^=ar ; return ans ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...