Submission #1272009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272009		thuhienne	Game (IOI14_game)	C++20	100 / 100	214 ms	15928 KiB

game

#include "game.h"

int root[1509],size[1509],edge[1509][1509],n;
//root i: dsu bth
//edge i j: da co bao nhieu canh duoc hoi giua 2 tplt co i lam root va j lam root

void initialize(int _n) {
	n = _n;
	for (int i = 0;i < n;i++) root[i] = i,size[i] = 1;
}

int getroot(int node) {
	return (node == root[node] ? node : root[node] = getroot(root[node]));
}

int hasEdge(int u, int v) {
	int ru = getroot(u),rv = getroot(v);
	
	edge[ru][rv]++;edge[rv][ru]++;
	
	if (edge[ru][rv] == size[ru] * size[rv]) {
		root[ru] = rv;
		size[rv] += size[ru];
		for (int i = 0;i < n;i++) {
			edge[i][rv] += edge[i][ru];
			edge[rv][i] += edge[ru][i];
		}
		return 1;
	} else return 0;
}

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