Submission #283284

#	Time	Username	Problem	Language	Result	Execution time	Memory
283284		GREGOIRELC	Game (IOI14_game)	C++14	100 / 100	448 ms	16632 KiB

game

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

using namespace std;

const int MAX_NOEUD = 15e2;

int nbNoeud;
int nbArcRelie[MAX_NOEUD];
bool appartient[MAX_NOEUD];
bool reliePossible[MAX_NOEUD][MAX_NOEUD];

void initialize(int n)
{
	nbNoeud = n;
	for(int i = 0; i < nbNoeud; i++)
	{
		for(int j = 0; j < nbNoeud; j++)
		{
			reliePossible[i][j] = true;
		}
		reliePossible[i][i] = false;
		nbArcRelie[i] = 1;
	}
	nbArcRelie[0] = 0;
	appartient[0] = true;
}

int hasEdge(int u, int v)
{
	reliePossible[u][v] = false;
	reliePossible[v][u] = false;
	if(appartient[u] && appartient[v])
	{
		return 0;
	}
	if(appartient[v])
	{
		swap(u, v);
	}
	if(appartient[u])
	{
		nbArcRelie[v]--;
		if(nbArcRelie[v] == 0)
		{
			appartient[v] = true;
			for(int i = 0; i < nbNoeud; i++)
			{
				if(reliePossible[v][i])
				{
					nbArcRelie[i]++;
				}
			}
			return 1;
		}
	}
	return 0;
}	

• Subtask 1: 15 / 15
• Subtask 2: 27 / 27
• Subtask 3: 58 / 58