Submission #168342

#	Time	Username	Problem	Language	Result	Execution time	Memory
168342		johutha	Game (IOI14_game)	C++14	15 / 100	2 ms	424 KiB

game

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

using namespace std;

struct unionfind
{
	vector<int> boss;

	int find(int x)
	{
		if (boss[x] == x) return x;
		return boss[x] = find(boss[x]);
	}

	void unite(int a, int b)
	{
		if (rand() % 2 == 0)
		{
			boss[find(a)] = find(b);
		}
		else
		{
			boss[find(b)] = find(a);
		}
	}

	void init(int n)
	{
		boss.resize(n);

		for (int i = 0; i < n; i++)
		{
			boss[i] = i;
		}
	}
};

struct graph
{
	int n;
	vector<vector<int>> conns;
	unionfind uf;

	void init(int in)
	{
		n = in;
		uf.init(n);
		conns.resize(n, vector<int>(n, 1));
	}

	int& conn(int a, int b)
	{
		return conns[max(a, b)][min(a, b)];
	}

	void addedge(int a, int b)
	{
		vector<int> newvals(n);

		for (int i = 0; i < n; i++)
		{
			newvals[i] = -1;
			if (uf.find(i) == i && i != a && i != b)
			{
				newvals[i] = conn(a, i) + conn(b, i);
			}
		}

		uf.unite(a, b);
		for (int i = 0; i < n; i++)
		{
			if (newvals[i] != -1)
			{
				conn(i, uf.find(a)) = newvals[i];
			}
		}
	}

	void unadd(int a, int b)
	{
		conn(uf.find(a), uf.find(b))--;
	}

	bool shouldadd(int a, int b)
	{
		return conn(uf.find(a), uf.find(b)) == 1;
	}
};

graph g;

void initialize(int n)
{
	g.init(n);
}

int hasEdge(int u, int v) 
{
    if (g.shouldadd(u, v))
	{
		g.addedge(u, v);
		return 1;
	}
	else
	{
		g.unadd(u, v);
		return 0;
	}
}

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