Submission #518873

#	Time	Username	Problem	Language	Result	Execution time	Memory
518873		tjd229	Game (IOI14_game)	C++14	15 / 100	1 ms	468 KiB

game

#include "game.h"
int n;
int p[1500];
int mat[1500][1500],mem[1500][1500];
int sz[1500];
int find(int a) {
	if (p[a] != a) p[a] = find(p[a]);
	return p[a];
}
bool dsu(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return false;
	sz[a] += sz[b];
	p[b] = a;
	for (int i = 0; i < n; ++i) {
		int par = find(i);
		if(par!=a)
			mat[a][i] += mat[b][i],mat[i][a]+=mat[i][b];
	}
	return true;
}
void initialize(int n) {
	::n = n;
	for (int i = 0; i < n; ++i) {
		sz[i] = 1; p[i] = i;
		for (int j = 0; j < n; ++j) mem[i][j] =mem[j][i]= -1;
	}
}

int hasEdge(int u, int v) {
	if (mem[u][v] == -1) {
		int U = find(u), V = find(v);
		//if (U == V) return 0;
		if (sz[U] * sz[V] - 1 == mat[U][V]) {
			mem[u][v] = mem[v][u] = 1;
			dsu(U, V);
		}
		else {
			++mat[U][V]; ++mat[V][U];
			mem[u][v] = mat[v][u] = 0;
		}
	}
	return mem[u][v];
	
}

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