Submission #871276

#	Time	Username	Problem	Language	Result	Execution time	Memory
871276		NintsiChkhaidze	Game (IOI14_game)	C++17	100 / 100	303 ms	26588 KiB

game

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

const int N = 1505;
int p[N],sz[N],cnt[N][N],n;
bool f[N];

int P(int x){
	if (x == p[x]) return x;
	return p[x] = P(p[x]);
}

void dsu(int x,int y){
	int px=P(x),py = P(y);
	if (px==py) return;
	
	if (sz[px] < sz[py]) swap(px,py);
	sz[px] += sz[py];
	sz[py] = 0;
	p[py] = px;
	
	for (int i = 1; i <= n; i++){
		int par = P(i);
		if (par != px && !f[par]) {
			f[par] = 1;
			cnt[px][par] += cnt[py][par];
			cnt[par][px] = cnt[px][par];
		}
	}
	for (int i = 1; i <= n; i++)
		f[i] = 0;
	
}
void initialize (int m) {
	n = m;
	for (int i = 1; i <= n; i++){
		p[i] = i;
		sz[i] = 1;
	}
}

int hasEdge(int u, int v) {
    u = P(u+1);
    v = P(v+1);
    cnt[u][v]++;
    cnt[v][u]++;
    if (u != v && cnt[u][v] == sz[u] * sz[v]){
    	dsu(u,v);
    	return 1;
	}
	return 0;
}

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