Submission #646595

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
646595	2022-09-30T09:22:27 Z	jamezzz	Toy Train (IOI17_train)	C++17	0 / 100	1031 ms	1724 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]==0&&a[u]==1&&all)cycle[u]=true;
	else if(r[u]==0&&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,done=true;
			for(int v:AL[u]){
				if(v==u)continue;
				if(good[v]==1)have=true;
				else if(good[v]==0)all=false;
				else done=false;
			}
			if(a[u]==1)good[u]=have,take=true;
			else if(done)good[u]=all,take=true;
		}
		if(!take)break;
	}
	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	280 ms	1336 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	Incorrect	1 ms	340 KB	3rd lines differ - on the 5th token, expected: '1', found: '-1'
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	207 ms	1724 KB	Output is correct
2	Correct	187 ms	1564 KB	Output is correct
3	Correct	178 ms	1508 KB	Output is correct
4	Incorrect	962 ms	1464 KB	3rd lines differ - on the 1st token, expected: '1', found: '0'
5	Halted	0 ms	0 KB	-