Submission #132630

#	Time	Username	Problem	Language	Result	Execution time	Memory
132630		junodeveloper	Game (IOI14_game)	C++14	100 / 100	516 ms	25336 KiB

game

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

int N, par[1500], rk[1500];
int cnt[1500][1500], sz[1500];

int pn(int u){return u==par[u]?u:pn(par[u]); }
void us(int a, int b) {
	a=pn(a), b=pn(b);
	if(rk[a]<rk[b]) swap(a,b);
	par[b]=a;
	sz[a]+=sz[b];
	for(int v=0; v<N; v++)
		cnt[min(a,v)][max(a,v)]+=cnt[min(b,v)][max(b,v)];
	if(rk[a]==rk[b])rk[a]++;
}

void initialize(int n) {
	N=n;
	int i, j;
	for(i=0; i<n; i++) { 
		for(j=0; j<n; j++) cnt[i][j] = 0;
		par[i] = i;
		rk[i] = 0;
		sz[i] = 1;
	}
}

int hasEdge(int u, int v) {
	u=pn(u),v=pn(v);
	if(u==v) return 1;
	else if(u>v) swap(u,v);
	cnt[u][v]++;
	if(cnt[u][v]==sz[u]*sz[v]) {
		us(u,v);
		return 1;
	}
	return 0;
}

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