Submission #110616

#	Time	Username	Problem	Language	Result	Execution time	Memory
110616		MegaOwIer	Toy Train (IOI17_train)	C++14	100 / 100	404 ms	1536 KiB

train

#include<bits/stdc++.h>
using namespace std;
const int MX=5005,MN=20005;
typedef vector<int> Array;

int N,M,deg[MX],need[MX];
Array pre[MX],ans;
bool flag;

void dfs(int u,Array& w)
{
	for(int i:pre[u])
	{
		need[i]--;
		if(!w[i]&&!need[i])dfs(i,w);
	}
}

Array who_wins(Array a,Array r,Array u,Array v)
{
	N=a.size(),M=u.size();
	for(int i=0;i<N;i++)ans.push_back(true); 
	for(int i=0;i<M;i++)pre[v[i]].push_back(u[i]),deg[u[i]]++;
	while(!flag)
	{
		flag=1;
		for(int i=0;i<N;i++)need[i]=(a[i]?1:deg[i]);
		for(int i=0;i<N;i++)if(r[i]&&ans[i])dfs(i,r);
		for(int i=0;i<N;i++)if(r[i]&&ans[i]&&need[i]>0)
			ans[i]=false,flag=false;
	}
	for(int i=0;i<N;i++)ans[i]&=(need[i]<=0);
	return ans;
}

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