Submission #257166

#	Time	Username	Problem	Language	Result	Execution time	Memory
257166		GREGOIRELC	Toy Train (IOI17_train)	C++14	0 / 100	2090 ms	1152 KiB

train

#include "train.h"
#include <iostream>

using namespace std;

const int MAX_NOEUD = 5e3;
const int MAX_ARC = 2e4;

int nbNoeud, nbArc;
bool estProprietaire[MAX_NOEUD];
bool estRechargeable[MAX_NOEUD];
bool dp[MAX_NOEUD];
vector<int> graphe[MAX_NOEUD];
vector<int> pile;
vector<int> result;

bool DFS(int curNoeud)
{
	if(dp[curNoeud])
	{
		for(int i = (int)pile.size() - 1; i > -1; i--)
		{
			if(estRechargeable[pile[i]])
			{
				return true;
			}
			if(pile[i] == curNoeud)
			{
				return false;
			}
		}
	}
	dp[curNoeud] = true;
	pile.push_back(curNoeud);
	for(int voisin : graphe[curNoeud])
	{
		bool val = DFS(voisin);
		if(!val && !estProprietaire[curNoeud])
		{
			return false;
		}
		if(val && estProprietaire[curNoeud])
		{
			return true;
		}
	}
	pile.pop_back();
	dp[curNoeud] = false;
	if(graphe[curNoeud].size() == 0)
	{
		return false;
	}
	return !estProprietaire[curNoeud];
}

vector<int> who_wins(vector<int> a, vector<int> r, vector<int> u, vector<int> v)
{
	nbNoeud = (int)a.size();
	nbArc = (int)u.size();
	
	for(int iNoeud = 0; iNoeud < nbNoeud; iNoeud++)
	{
		if(a[iNoeud] == 1)
		{
			estProprietaire[iNoeud] = true;
		}
		if(r[iNoeud])
		{
			estRechargeable[iNoeud] = true;
		}
	}
	for(int iArc = 0; iArc < nbArc; iArc++)
	{
		graphe[u[iArc]].push_back(v[iArc]);
	}

	for(int iDep = 0; iDep < nbNoeud; iDep++)
	{
		if(DFS(iDep))
		{
			result.push_back(1);
		}
		else
		{
			result.push_back(0);
		}
		pile.clear();
		for(int i = 0; i < nbNoeud; i++)
		{
			dp[i] = false;
		}
	}
	return result;
}

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