Submission #100394

#	Time	Username	Problem	Language	Result	Execution time	Memory
100394		luciocf	Game (IOI14_game)	C++14	42 / 100	1079 ms	6692 KiB

game

#include <bits/stdc++.h>
#include "game.h"

using namespace std;

const int maxn = 1510;

typedef pair<int, int> pii;

int pai[maxn], peso[maxn];

set<pii> relation;

int Find(int x)
{
	if (pai[x] == x) return x;
	return pai[x] = Find(pai[x]);
}

void Join(int x, int y)
{
	x = Find(x), y = Find(y);
	if (x == y) return;

	if (peso[x] < peso[y]) swap(x, y);

	pai[y] = x, peso[x] += peso[y];
}

void initialize(int n) 
{
	for (int i = 0; i < n; i++) pai[i] = i;

	for (int i = 0; i < n; i++)
		for (int j = i+1; j < n; j++)
			relation.insert({i, j});
}

int hasEdge(int u, int v) 
{
	if (Find(u) == Find(v)) return 0;

	int cu = Find(u), cv = Find(v);

	for (auto E: relation)
	{
		int a = E.first, b = E.second;
		int ca = Find(a), cb = Find(b);

		if ((a == u && b == v) || (a == v && b == u)) continue;

		if ((ca == cu && cb == cv || ca == cv && cb == cu))
		{
			if (relation.find({u, v}) != relation.end()) relation.erase({u, v});
			if (relation.find({v, u}) != relation.end()) relation.erase({v, u});

			return 0;
		}
	}

	if (relation.find({u, v}) != relation.end()) relation.erase({u, v});
	if (relation.find({v, u}) != relation.end()) relation.erase({v, u});

	Join(u, v);

	return 1;
}

Compilation message (stderr)

game.cpp: In function 'int hasEdge(int, int)':
game.cpp:52:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if ((ca == cu && cb == cv || ca == cv && cb == cu))
        ~~~~~~~~~^~~~~~~~~~~

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