Submission #944507

#	Time	Username	Problem	Language	Result	Execution time	Memory
944507		4QT0R	Game (IOI14_game)	C++17	100 / 100	273 ms	26704 KiB

game

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

int n;
int lider[1503];
int siz[1503];
int zap[1503][1503];

void initialize(int rozmiar){
	n=rozmiar;
	for (int i = 0; i<n; i++){
		lider[i]=i;
		siz[i]=1;
	}
}

int Find(int v){
	if (lider[v]==v)return v;
	lider[v]=Find(lider[v]);
	return lider[v];
}

void Union(int a, int b){
	a=Find(a);
	b=Find(b);
	if (a==b)return;
	if (siz[a]<siz[b])swap(a,b);
	lider[b]=a;
	siz[a]+=siz[b];
	for (int i = 0; i<n; i++){
		if (i==a)continue;
		zap[a][i]+=zap[b][i];
		zap[i][a]+=zap[i][b];
	}
}

int hasEdge(int u, int v){
	u=Find(u);
	v=Find(v);
	if (u==v)return 0;
	zap[v][u]++;
	zap[u][v]++;
	if (siz[v]*siz[u]>zap[v][u])return 0;
	else{
		Union(u,v);
		return 1;
	}
}

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