Submission #228477

#	Time	Username	Problem	Language	Result	Execution time	Memory
228477		bharat2002	Game (IOI14_game)	C++14	100 / 100	497 ms	25448 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1510;
int deg[N][N], p[N], srank[N];
int n;
void initialize(int NC)
{
	n=NC;
	for(int i=1;i<=n;i++) 
	{	for(int j=1;j<=n;j++) deg[i][j]=0;
		srank[i]=1;p[i]=i;
	}
}
int find(int x)
{
	if(p[x]!=x) p[x]=find(p[x]);
	return p[x];
}
void UNION(int a, int b)
{
	if(srank[a]<srank[b]) swap(a, b);
	srank[a]+=srank[b];p[b]=a;
	for(int i=1;i<=n;i++) deg[a][i]+=deg[b][i];
	for(int i=1;i<=n;i++) deg[i][a]=deg[a][i];
}
int hasEdge(int u, int v)
{
	u++;v++;
	int tu=find(u), tv=find(v);
	int tot=srank[tu]*srank[tv];deg[tu][tv]++;deg[tv][tu]++;
	if(deg[tu][tv]==tot)
	{
		UNION(tu, tv);return 1;
	}
	return 0;
}

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