Submission #646584

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
646584	2022-09-30T08:37:30 Z	jamezzz	Toy Train (IOI17_train)	C++17	0 / 100	1035 ms	1884 KB

train

#include "train.h"
#include <bits/stdc++.h>
using namespace std;

#define maxn 5005
typedef vector<int> vi;

bool vis[maxn],cycle[maxn];
int good[maxn];
vi AL[maxn],a,r,u,v;

bool dfs(int u,int rt){
	vis[u]=true;
	bool have=false,all=true;
	for(int v:AL[u]){
		if(v==rt){
			have=true;
			continue;
		}
		if(!vis[v])dfs(v,rt);
		else if(!cycle[v])all=false;
		else have=true;
	}
	if(a[u]==1&&have)cycle[u]=true;
	else if(a[u]==0&&all)cycle[u]=true;
	return cycle[u];
}

bool dfs2(int u,int rt){
	vis[u]=true;
	bool have=false,all=true;
	for(int v:AL[u]){
		if(v==rt){
			have=true;
			continue;
		}
		if(!vis[v])dfs2(v,rt);
		if(!cycle[v])all=false;
		else have=true;
	}
	if(r[u]!=1&&a[u]==1&&all)cycle[u]=true;
	else if(r[u]!=1&&a[u]==0&&have)cycle[u]=true;
	return cycle[u];
}

vi who_wins(vi _a,vi _r,vi _u,vi _v){
	a=_a,r=_r,u=_u,v=_v;
	int n=a.size(),m=u.size();
	for(int i=0;i<m;++i){
		AL[u[i]].push_back(v[i]);
	}
	memset(good,-1,sizeof good);
	for(int i=0;i<n;++i){
		for(int j=0;j<n;++j)vis[j]=cycle[j]=false;
		if(r[i]==1&&dfs(i,i))good[i]=1;
		else if(r[i]==0&&dfs2(i,i))good[i]=0;
	}
	for(int i=0;i<n;++i){
		bool take=false;
		for(int u=0;u<n;++u){
			if(good[u]!=-1)continue;
			bool have=false,all=true;
			for(int v:AL[u]){
				if(good[v]==1)have=true;
				else if(good[v]==0)all=false;
			}
			if(a[u]==1)good[u]=have;
			else good[u]=all;
			take=true;
		}
		if(!take)continue;
	}
	vi ans(n,0);
	for(int i=0;i<n;++i)ans[i]=good[i];
	return ans;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Incorrect	1 ms	340 KB	3rd lines differ - on the 3rd token, expected: '0', found: '1'
3	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	214 ms	1748 KB	Output is correct
2	Correct	198 ms	1884 KB	Output is correct
3	Correct	196 ms	1716 KB	Output is correct
4	Incorrect	975 ms	1740 KB	3rd lines differ - on the 1st token, expected: '1', found: '0'
5	Halted	0 ms	0 KB	-