Submission #139496

#	Time	Username	Problem	Language	Result	Execution time	Memory
139496		arthurconmy	Toy Train (IOI17_train)	C++14	0 / 100	878 ms	1592 KiB

train

#include <bits/stdc++.h>
#ifndef ARTHUR_LOCAL
	#include "train.h"
#endif

using namespace std;

const int MAXN = 5000;

bool is_gen[MAXN];
bool vis[MAXN];
bool local_vis[MAXN];
vector<int> adj[MAXN];
int cur_gen=0;
int start=0;
int gen[MAXN];

bool dfs(int v)
{
	if(is_gen[v]) cur_gen++;
	gen[v]=cur_gen;
	vis[v]=1;
	local_vis[v]=1;

	for(auto u:adj[v])
	{
		if(local_vis[u] && cur_gen>0 && (gen[v]!=gen[u] || is_gen[u]==1)) return 1; 
		if(vis[u]) continue;

		bool cur=dfs(u);
		if(cur) return 1;
	}

	if(is_gen[v]) cur_gen--;
	local_vis[v]=0;

	return 0;
}

vector<int> who_wins(vector<int> A, vector<int> R, vector<int> U, vector<int> V)
{
	int n = A.size();
	int m = U.size();

	for(int i=0; i<n; i++) is_gen[i]=R[i];

	for(int i=0; i<m; i++)
	{
		adj[U[i]].push_back(V[i]);
	}

	vector<int> ans;

	for(int i=0; i<n; i++)
	{
		cur_gen=0;
		start=i;
		for(int i=0; i<n; i++)
		{
			vis[i]=0;
			local_vis[i]=0;
			gen[i]=0;
		}

		ans.push_back(dfs(i));
	}

	return ans;
}

#ifdef ARTHUR_LOCAL
	int main()
	{
		for(auto e:who_wins({0,1},{0,1},{0,0,1,1},{0,1,0,1}))
		{
			cout << e << endl;
		}
	}
#endif

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