Submission #1014017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014017		parsadox2	Game (IOI14_game)	C++17	100 / 100	393 ms	17236 KiB

game

#include <bits/stdc++.h>

#include "game.h"

using namespace std;

const int N = 15e2 + 10;
int cnt[N][N] , n;

struct DSU{
	int par[N];
	void Build()
	{
		for(int i = 0 ; i < n ; i++)
			par[i] = i;
	}
	int root(int v)
	{
		return (par[v] == v ? v : par[v] = root(par[v]));
	}
	void Merge(int a , int b)
	{
		int ra = root(a);
		int rb = root(b);
		par[rb] = ra;
	}
} dsu;

void initialize(int nn)
{
	n = nn;
	for(int i = 0 ; i < n ; i++)  for(int j = 0 ; j < n ; j++)
		cnt[i][j] = 1;
	dsu.Build();
}

void Merge(int a , int b)
{
	for(int i = 0 ; i < n ; i++)
	{
		cnt[a][i] += cnt[b][i];
		cnt[i][a] += cnt[i][b];
	}
	dsu.Merge(a , b);
}

int hasEdge(int a , int b)
{
	int ra = dsu.root(a) , rb = dsu.root(b);
	cnt[ra][rb]--;
	cnt[rb][ra]--;
	if(cnt[ra][rb] != 0)
		return 0;
	Merge(ra , rb);
	return 1;
}

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