Submission #545402

#	Time	Username	Problem	Language	Result	Execution time	Memory
545402		benson1029	Game (IOI14_game)	C++14	100 / 100	344 ms	24824 KiB

game

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

int dsu[1505];
int cnt[1505][1505];
int N;

int find(int x) {
	if(dsu[x]==x) return x;
	return dsu[x] = find(dsu[x]);
}


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

int hasEdge(int u, int v) {
	int x = find(u), y = find(v);
    if(cnt[min(x, y)][max(x, y)] == 1) {
    	for(int i=0; i<N; i++) {
			cnt[min(i, y)][max(i, y)] += cnt[min(i, x)][max(i, x)];
		}
		for(int i=0; i<N; i++) {
			cnt[min(i, x)][max(i, x)] = 0;
		}
    	dsu[x] = y;
    	return 1;
	}
	cnt[min(x, y)][max(x, y)]--;
	return 0;
}

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