Submission #231265

#	Time	Username	Problem	Language	Result	Execution time	Memory
231265		peijar	Game (IOI14_game)	C++17	100 / 100	542 ms	25336 KiB

game

#include <bits/stdc++.h>
using namespace std;

#define SZ(v) ((int)(v).size())
using ll = long long;

/*
	Si les deux sommets sont connectes : on peut repondre comme on veut !
	si chemin entre deux sommets mais on a pas demande arete entre les deux sommets -> impossible !!

	A quelle condition mettre une arete entre u et v
	Soit U et V les cc respectives de u, v. U != V 
	Si c'est la derniere arete entre U et V : on la met 
	Sinon, on la met pas
	graphe connexe seulement apres la derniere arete !
*/

void initialize(int n);
int hasEdge(int u, int v);

int nb_sommets;
const int MAXSOMMETS = 1500;
int id[MAXSOMMETS];
int nb_questions[MAXSOMMETS][MAXSOMMETS];
int sz[MAXSOMMETS];

void initialize(int n)
{
	nb_sommets = n;
	for (int i(0); i < n; ++i)
	{
		id[i] = i;
		sz[i] = 1;
	}
}

int find(int u)
{
	if (id[u] == u) return u;
	return id[u] = find(id[u]);
}

void merge(int u, int v)
{
	u = find(u), v = find(v);
	if (sz[v] > sz[u]) swap(u, v);
	for (int i(0); i < nb_sommets; ++i)
	{
		nb_questions[u][i] += nb_questions[v][i];
		nb_questions[i][u] += nb_questions[i][v];
	}
	sz[u] += sz[v];
	id[v] = u;
}

int hasEdge(int u, int v)
{
	u = find(u);
	v = find(v);
	if (u == v)
		return 1;
	nb_questions[u][v]++;
	nb_questions[v][u]++;
	if (nb_questions[u][v] == (sz[u] * sz[v]))
	{
		merge(u,v);
		return 1;
	}
	return 0;
}

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