Submission #646584

#	Time	Username	Problem	Language	Result	Execution time	Memory
646584		jamezzz	Toy Train (IOI17_train)	C++17	0 / 100	1035 ms	1884 KiB

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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51