Submission #118876

#	Time	Username	Problem	Language	Result	Execution time	Memory
118876		andremfq	Game (IOI14_game)	C++17	42 / 100	1085 ms	15788 KiB

game

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

set<int> s[MAXN];
int n,U,V,pai[MAXN],prof[MAXN],marc[MAXN][MAXN];

void initialize(int n)
{
	for(int i=0;i<n;i++)
	{
		pai[i]=i;
		marc[i][i]=1;
		prof[i]=1;
		for(int j=i+1;j<n;j++)
			s[i].insert(j),	s[j].insert(i);
	}	
}

void see()
{
	for(int i=0;i<n;i++)
	{
		set<int> :: iterator it;
		printf("U = %d : \n",i);
		for(it=s[i].begin();it!=s[i].end();it++)
			printf("%d ",*it);
		printf("\n\n");
	}
}

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;
	
	set<int> :: iterator it;
	
	if(prof[a]>prof[b])
	{	
		for(it=s[b].begin();it!=s[b].end();it++)	s[a].insert(*it);
		pai[b]=a;
		prof[a]+=prof[b];
		s[a].insert(b);	
		return;
	}
	
	for(it=s[a].begin();it!=s[a].end();it++)	s[b].insert(*it);
	s[b].insert(a);
	pai[a]=b;
	prof[b]+=prof[a];
}

int hasEdge(int u,int v)
{	
	set<int> :: iterator it;
	for(it=s[fd(u)].begin();it!=s[fd(u)].end();it++)
	{
		if(*it!=u && *it!=v && s[fd(v)].find(*it)!=s[fd(v)].end())
		{
//			printf("pai[%d] = %d   pai[%d] = %d\n",u,fd(u),v,fd(v));
//			see();
			s[fd(u)].erase(v), s[fd(v)].erase(u);
			return 0;
		}
	}
//	printf("pai[%d] = %d   pai[%d] = %d\n",u,fd(u),v,fd(v));
//	see();
	join(u,v);
	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: 15 / 15
• Subtask 2: 27 / 27
• Subtask 3: 0 / 58