Submission #360951

#	Time	Username	Problem	Language	Result	Execution time	Memory
360951		jesus_coconut	Game (IOI14_game)	C++17	100 / 100	558 ms	25436 KiB

game

#include <bits/stdc++.h>
#include "game.h"

using namespace std;

int n;

struct DSU {
	vector<int> par, rank, setsize;
	int numsets;
	vector<vector<int>> con;

	explicit DSU(int n) {
		par.assign(n, 0);
		iota(begin(par), end(par), 0);
		rank.assign(n, 0);
		setsize.assign(n, 1);
		con.assign(n, vector<int>(n));
		numsets = n;
	}

	int findSet(int x) { return (par[x] == x) ? x : (par[x] = findSet(par[x])); }

	bool sameSet(int x, int y) { return findSet(x) == findSet(y); }

	bool unite(int x, int y) {
		if (sameSet(x, y)) return false;
		x = findSet(x), y = findSet(y);
		if (rank[x] > rank[y]) swap(x, y);
		par[x] = y;
		for (int i = 0; i < n; ++i) {
			con[y][i] += con[x][i];
			con[i][y] = con[y][i];
		}
		if (rank[x] == rank[y]) ++rank[y];
		setsize[y] += setsize[x];
		--numsets;
		return true;
	}
};

DSU dsu(1);
void initialize(int n) {
	::n = n;
	dsu = DSU(n);
}


int hasEdge(int u, int v) {
    int a = dsu.findSet(u);
    int b = dsu.findSet(v);

	dsu.con[a][b]++;
	dsu.con[b][a]++;

    if (dsu.con[a][b] == dsu.setsize[a] * dsu.setsize[b]) {
    	dsu.unite(a, b);
    	return 1;
    } else {
    	return 0;
    }
}

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