Submission #121659

#	Time	Username	Problem	Language	Result	Execution time	Memory
121659		andremfq	Game (IOI14_game)	C++17	0 / 100	2 ms	384 KiB

game

#include<bits/stdc++.h>
#include "game.h"
using namespace std;
const int MAXN=1510;

int n,U,V,pai[MAXN],prof[MAXN],q[MAXN][MAXN];

void initialize(int n)
{
	for(int i=0;i<n;i++)
	{
		pai[i]=i;
		for(int j=i+1;j<n;j++)
			q[i][j]=1,	q[j][i]=1;
	}	
}

int fd(int v)
{
	if(v==pai[v])	return v;
	return pai[v]=fd(pai[v]);
}

void join(int a,int b)
{
	a=fd(a);	b=fd(b);
	if(a==b)	return;
	
	if(prof[a]>prof[b])		swap(a,b);
	
	for(int i=0;i<n;i++)	
	{
		q[b][i]+=q[a][i];
		if(i!=a && i!=b)	q[i][b]+=q[i][a];
	}
	
	pai[a]=b;
	
	if(prof[a]==prof[b])	prof[b]++;
}

int hasEdge(int u,int v)
{	
	int U=fd(u),	V=fd(v);
	if(U==V){/*printf("BLABLA\n");*/	return 0;	}
	if(q[U][V]>1 || q[V][U]>1)
	{
//		printf("pai[%d] = %d  pai[%d] = %d\n",u,U,v,V);
//		printf("q = %d   q = %d\n",q[U][V],q[V][U]);
		q[U][V]--;	q[V][U]--;
		return 0;
	}
	
	join(u,v);
//	printf("q = %d   q = %d\n",q[U][V],q[V][U]);
	return 1;
}
/*
int main ()
{
	scanf("%d",&n);
	
	initialize(n);
	
	for(int i=0;i<n*(n-1)/2;i++)
	{
		scanf("%d %d",&U,&V);
		
		printf("%d\n",hasEdge(U,V));
	}
}
*/

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