Submission #299631

#	Time	Username	Problem	Language	Result	Execution time	Memory
299631		REALITYNB	Toy Train (IOI17_train)	C++14	0 / 100	1309 ms	1932 KiB

train

#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  ; 
		}
	}
	for(int i=0;i<n;i++){
		vector<int> v(5001) ; 
		res= 0 ; 
		propa(i,0,v) ; 
		is[i]= res ; 
	}
	ar^=1 ; 
	vector<int> ans(n) ;
	for(int i=0;i<n;i++) ans[i]=is[i]^ar ; 
	return ans ; 
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51