Submission #299631

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
299631	2020-09-15T11:10:08 Z	REALITYNB	Toy Train (IOI17_train)	C++14	0 / 100	1309 ms	1932 KB

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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	227 ms	1360 KB	3rd lines differ - on the 14th token, expected: '1', found: '0'
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	640 KB	3rd lines differ - on the 8th token, expected: '0', found: '1'
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	185 ms	1932 KB	Output is correct
2	Correct	210 ms	1912 KB	Output is correct
3	Correct	219 ms	1912 KB	Output is correct
4	Correct	1309 ms	1788 KB	Output is correct
5	Incorrect	824 ms	1784 KB	3rd lines differ - on the 1st token, expected: '1', found: '0'
6	Halted	0 ms	0 KB	-