Submission #222755

#	Time	Username	Problem	Language	Result	Execution time	Memory
222755		MohamedAhmed04	Game (IOI14_game)	C++14	100 / 100	515 ms	25380 KiB

game

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

using namespace std ;

const int MAX = 1500 + 10 ;

int par[MAX] , sz[MAX] , cnt[MAX][MAX] ;

int N ;

void init()
{
	for(int i = 0 ; i <= N ; ++i)
		par[i] = i , sz[i] = 1 ;
}

int root(int node)
{
	if(par[node] == node)
		return node ;
	return (par[node] = root(par[node])) ;
}

int prv , now ;

void Union(int x , int y)
{
	int a = root(x) ;
	int b = root(y) ;
	if(sz[a] < sz[b])
		swap(a , b) ;
	prv = b ;
	now = a ;
	sz[a] += sz[b] ;
	par[b] = a ;
}

void initialize(int n) 
{
	N = n ;
	init() ;
	return ;
}

int hasEdge(int u, int v) 
{
	int a = root(u) ;
	int b = root(v) ;
	if(a == b)
		return 0 ;
	if(sz[a] * sz[b] != cnt[a][b]+1)
	{
		cnt[a][b]++ ;
		cnt[b][a]++ ;
		return 0 ;
	}
	Union(u , v) ;
	for(int i = 0 ; i < N ; ++i)
	{
		cnt[i][now] += cnt[i][prv] ;
		cnt[now][i] = cnt[i][now] ;
		cnt[i][prv] = cnt[prv][i] = 0 ;
	}
    return 1 ;
}

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