Submission #165359

#	Time	Username	Problem	Language	Result	Execution time	Memory
165359		Berted	Game (IOI14_game)	C++14	100 / 100	735 ms	34248 KiB

game

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

using namespace std;

int mtx[1501][1501]={};
int ask[1501][1501]={};
int pr[1501]={},sz[1501]={},n;

int fn(int x)
{
	return pr[x] = (pr[x] - x)?fn(pr[x]):x;
}

void jn(int a,int b)
{
	a = fn(a), b = fn(b);
	if (a != b)
	{
		pr[b] = a;
		sz[a] += sz[b];
		for (int i = 0; i < n; i++)
		{
			ask[a][i] += ask[b][i];
			ask[i][a] += ask[i][b];
		}
	}
}

void initialize(int n) 
{
	::n = n;
	for (int i=0;i<n;i++)
	{
		for (int j = 0;j<n;j++)
		{
			mtx[i][j] = -1;
		}
		pr[i] = i;
		sz[i] = 1;
	}
}

int hasEdge(int u, int v) 
{
   	if (mtx[u][v]==-1)
    {
    	int tu = u,tv = v;
    	u = fn(u),v = fn(v);
    	ask[u][v]++;ask[v][u]++;
    	if (ask[u][v] == sz[u] * sz[v]) {jn(u,v);mtx[tu][tv] = 1;mtx[tv][tu] = 1;}
    	else {mtx[tu][tv] = 0;mtx[tv][tu] = 0;}
    	u = tu, v = tv;
    }
    return mtx[u][v];
}

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