Submission #162857

#	Time	Username	Problem	Language	Result	Execution time	Memory
162857		lukameladze	Game (IOI14_game)	C++14	100 / 100	488 ms	25456 KiB

game

# include <bits/stdc++.h>
using namespace std;
int N,a,b,d[2250001],p[2250001],mp[1505][1505];
void initialize(int n)
{
	N=n;
	for (int i=0; i<N; i++)
	{
	p[i]=i;
	d[i]=1;
	}
}
int get_col(int a)
{
	if (p[a]==a) return p[a];
   p[a]=get_col(p[a]);
   return p[a];
}
void col(long long a, long long b)
{
	b=get_col(b);
	a=get_col(a);
	if (a==b) return;
	d[b]+=d[a];
	d[a]=0;
	p[a]=b;
}
int hasEdge(int u ,int v)
{
		u=get_col(u);
		v=get_col(v);
		mp[u][v]++;
		mp[v][u]++;
		if (mp[u][v]==d[u]*d[v])
		{
			if (d[u]>=d[v]) swap(u,v);
			col(u,v);
			for (int i=0; i<N; i++)
			{
				mp[v][i]+=mp[u][i];
				mp[i][v]+=mp[i][u];
			}
			return 1;
		}
		else 
		return 0;
}

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