Submission #69500

#	Time	Username	Problem	Language	Result	Execution time	Memory
69500		E869120	Game (IOI14_game)	C++14	100 / 100	722 ms	159220 KiB

game

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

class MergeTech {
public:
	vector<int>group; vector<vector<int>>G, I; int sz = 0;

	void init(int size_) {
		sz = size_;
		group.resize(size_);
		G.resize(size_, vector<int>(0, 0));
		I.resize(size_, vector<int>(size_, 1));
		for (int i = 0; i < size_; i++) { G[i].push_back(i); group[i] = i; I[i][i] = 0; }
	}
	void unite(int u, int v) {
		u = group[u]; v = group[v];
		if (u == v) return;

		if (G[u].size() < G[v].size()) swap(u, v);

		for (int i = 0; i < G[v].size(); i++) { G[u].push_back(G[v][i]); group[G[v][i]] = u; }
		G[v].clear();
		for (int i = 0; i < sz; i++) { if (i != u && i != v) { I[u][i] += I[v][i]; I[v][i] = 0; } }
		for (int i = 0; i < sz; i++) { if (i != u && i != v) { I[i][u] += I[i][v]; I[i][v] = 0; } }
		I[u][v] = 0; I[v][u] = 0;
	}
	int query(int u, int v) {
		u = group[u]; v = group[v];
		if (u == v) return -1;
		return I[u][v];
	}
	void decrease(int u, int v) {
		u = group[u]; v = group[v];
		I[u][v]--; I[v][u]--;
	}
};

MergeTech UF;

void initialize(int n) {
	UF.init(n);
}

int hasEdge(int u, int v) {
	if (UF.query(u, v) == 1) {
		UF.unite(u, v);
		return 1;
	}
	UF.decrease(u, v);
	return 0;
}

Compilation message (stderr)

game.cpp: In member function 'void MergeTech::unite(int, int)':
game.cpp:22:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < G[v].size(); i++) { G[u].push_back(G[v][i]); group[G[v][i]] = u; }
                   ~~^~~~~~~~~~~~~

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