Submission #135080

#	Time	Username	Problem	Language	Result	Execution time	Memory
135080		arthurconmy	Game (IOI14_game)	C++14	42 / 100	1072 ms	5244 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 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;
}

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);

	for(int i=0; i<n; i++)
	{
		int i_emp = emp(i);
		if(i_emp != u_emp) continue;

		for(int j=0; j<n; j++)
		{
			int j_emp = emp(j);

			if(j_emp!=v_emp) continue;
			if(i==u && j==v) continue;

			if(state[i][j]!=-1)
			{
				state[u][v]=-1;
				state[v][u]=-1;

				#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;
}

// int main()
// {
// 	#ifdef ARTHUR_LOCAL
// 		ifstream cin("input.txt");
// 	#endif

// 	initialize(4);

// 	hasEdge(0,1);
// 	hasEdge(3,0);
// 	hasEdge(1,2);
// 	hasEdge(0,2);
// 	hasEdge(3,1);
// }

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