Submission #73929

#	Time	Username	Problem	Language	Result	Execution time	Memory
73929		Hoget157	Game (IOI14_game)	C++14	100 / 100	855 ms	158072 KiB

game

#include "game.h"
#include <iostream>
using namespace std;

int n,par[1510],rnk[1500],ok[1500][1500];

void initialize(int _n) {
	n = _n;
	for(int i = 0;i < n;i++){
		par[i] = i;
		rnk[i] = 0;
	}
	for(int i = 0;i < n;i++){
		for(int j = 0;j < n;j++) ok[i][j] = 1;
		ok[i][i] = 0;
	}
}

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

void unite(int x,int y){
	x = find(x);
	y = find(y);
	int a = x,b = y;
	if(rnk[x] < rnk[y]) par[x] = y;
	else{
		par[y] = x;
		if(rnk[x] == rnk[y]) rnk[x]++;
	}
	for(int i = 0;i < n;i++){
		int tmp = ok[i][a] + ok[i][b];
		ok[i][a] = 0;
		ok[i][b] = 0;
		ok[i][find(x)] = tmp;
		tmp = ok[a][i] + ok[b][i];
		ok[a][i] = 0;
		ok[b][i] = 0;
		ok[find(x)][i] = tmp;
	}
}

bool same(int x,int y){
	return find(x) == find(y);
}

int hasEdge(int u, int v) {
	int x = find(u),y = find(v);
	/*for(int i = 0;i < n;i++){
		for(int j = 0;j < n;j++) cout << ok[i][j] << " ";
		cout << endl;
	}*/
	if(x == y) return 1;
	ok[x][y]--;
	ok[y][x]--;
	if(!ok[x][y]){
		unite(u,v);
		return 1;
	}
	return 0;
}

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