Submission #30718

#	Time	Username	Problem	Language	Result	Execution time	Memory
30718		rondojim	Game (IOI14_game)	C++14	42 / 100	1000 ms	17028 KiB

game

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>
#include "game.h"
using namespace std;
 
const int maxn = 1505;
 
int n, P[maxn], orig[maxn];
set<pair<int, int>> undone;
 
inline int root(int x)
{
	return ((P[x] == x)?x:(P[x] = root(P[x])));
}
 
void dsu(int x, int y)
{
	x = root(x), y = root(y);
	P[y] = x;
}
 
void initialize(int _N)
{
	n = _N;
	for(int i = 0;i < n;i++)
	{
		P[i] = i;
		for(int j = i+1;j < n;j++) undone.insert({i, j});
	}
}
 
int hasEdge(int u, int v)
{
	if(u > v) swap(u, v);
 
	for(int i = 0;i < n;i++) orig[i] = P[i];
	dsu(u, v);
	bool cando = 1;
	for(auto it: undone)
	{
		if(it != make_pair(u, v))
		{
			if(root(it.first) == root(it.second))
			{
				cando = 0;
				break;
			}
		}
	}
	undone.erase({u, v});
	if(cando) return 1;
	else
	{
		for(int i = 0;i < n;i++) P[i] = orig[i];
		return 0;
	}
}

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