Submission #291388

#	Time	Username	Problem	Language	Result	Execution time	Memory
291388		TMJN	Game (IOI14_game)	C++17	100 / 100	563 ms	25368 KiB

game

#include "game.h"

int N;
int C[1500][1500];
int T[1500];

int par(int x){
	if(T[x]<0)return x;
	return T[x]=par(T[x]);
}

void uni(int x,int y){
	x=par(x);
	y=par(y);
	if(x==y)return;
	T[x]+=T[y];
	T[y]=x;
	for(int i=0;i<N;i++){
		C[i][x]+=C[i][y];
	}
	for(int i=0;i<N;i++){
		C[x][i]+=C[y][i];
	}
}

void initialize(int n) {
	N=n;
	for(int i=0;i<N;i++){
		T[i]=-1;
	}
}

int hasEdge(int u, int v) {
	u=par(u);
	v=par(v);
	if(C[u][v]==T[u]*T[v]-1){
		uni(u,v);
		return 1;
	}
	else{
		C[u][v]++;
		C[v][u]++;
		return 0;
	}
}

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