Submission #135086

#	Time	Username	Problem	Language	Result	Execution time	Memory
135086		arthurconmy	Game (IOI14_game)	C++14	100 / 100	793 ms	34172 KiB

game

#include <bits/stdc++.h>
using namespace std;

const int MAXN=1500;
int n;
int sz[MAXN];
int link[MAXN];
int state[MAXN][MAXN]; // 0 is undetermined
					   // 1 is connected
					   // -1 is disconnected

int echo[MAXN][MAXN];

int emp(int a)
{
	while(a!=link[a]) a=link[a];
	return a;
}

void join(int a, int b)
{
	a=emp(a);
	b=emp(b);
	if(a==b) return;

	if(sz[b]>sz[a]) swap(a,b);

	sz[a]+=sz[b];
	link[b]=a;

	// update echo[a][...] and echo[...][a]

	for(int i=0; i<n; i++)
	{
		echo[a][i] += echo[b][i];
		echo[i][a] += echo[b][i];
	}
}

void initialize(int n_raw)
{
	n=n_raw;

	for(int i=0; i<n; i++)
	{
		sz[i]=1;
		link[i]=i;
	}
}

int hasEdge(int u, int v)
{
	int u_emp = emp(u);
	int v_emp = emp(v);

	if(echo[u_emp][v_emp] != sz[u_emp]*sz[v_emp] - 1)
	{
		state[u][v]=-1;
		state[v][u]=-1;

		echo[u_emp][v_emp]++;
		echo[v_emp][u_emp]++;

		#ifdef ARTHUR_LOCAL
			// cout << state[i][j]i << " " << j << " ";
			cout << 0 << endl;
		#endif

		return 0;
	}

	state[u][v]=1;
	state[v][u]=1;
	join(u,v);

	#ifdef ARTHUR_LOCAL
		cout << 1 << endl;
	#endif

	return 1;
}

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