Submission #556686

#	Time	Username	Problem	Language	Result	Execution time	Memory
556686		Zanite	Game (IOI14_game)	C++17	100 / 100	438 ms	22640 KiB

game

#include "game.h"

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

struct DSU {
	int nodes;
	vector<int> par, sz;
	vector<vector<int>> edgeCount;

	DSU() {}

	DSU(int _nodes) {
		nodes = _nodes;
		par.assign(_nodes, 0);
		iota(par.begin(), par.end(), 0);
		sz.assign(_nodes, 1);
		edgeCount.assign(_nodes, vector<int>(_nodes));
	}

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

	void join(int x, int y) {
		int a = rep(x), b = rep(y);
		if (a == b) return;

		if (sz[a] > sz[b]) {
			par[b] = a;
			sz[a] += sz[b];
			for (int i = 0; i < nodes; i++) {
				edgeCount[a][i] += edgeCount[b][i];
				edgeCount[i][a] += edgeCount[i][b];
			}

		} else {
			par[a] = b;
			sz[b] += sz[a];
			for (int i = 0; i < nodes; i++) {
				edgeCount[b][i] += edgeCount[a][i];
				edgeCount[i][b] += edgeCount[i][a];
			}
		}
	}

	void addEdge(int x, int y) {
		edgeCount[rep(x)][rep(y)]++;
		edgeCount[rep(y)][rep(x)]++;
	}

	int countEdges(int x, int y) {
		return edgeCount[rep(x)][rep(y)];
	}

	int getSize(int x) {
		return sz[rep(x)];
	}
};

DSU D = DSU();

void initialize(int n) {
	D = DSU(n);
}

int hasEdge(int u, int v) {
    D.addEdge(u, v);
	//cout << D.countEdges(u, v) << ' ' << D.getSize(u) << ' ' << D.getSize(v) << '\n';
	if (D.countEdges(u, v) == D.getSize(u) * D.getSize(v)) {
		D.join(u, v);
		return 1;
	} else {
		return 0;
	}
}

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