Submission #351906

#	Time	Username	Problem	Language	Result	Execution time	Memory
351906		BlancaHM	Connecting Supertrees (IOI20_supertrees)	C++14	11 / 100	298 ms	24300 KiB

supertrees

#include <iostream>
#include <vector>
#include <unordered_map>
#include "supertrees.h"
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;

int root(int a, vector<int> & parent) {
	if (a == parent[a])
		return a;
	return parent[a] = root(parent[a], parent);
}

void merge(int i, int j, vector<int> & parent, vector<int> & rnk, int & numCCs) {
	int root_i = root(i, parent), root_j = root(j, parent);
	if (root_i == root_j) return;
	numCCs--;
	if (rnk[i] != rnk[j]) {
		if (rnk[i] > rnk[j]) parent[root_j] = parent[root_i];
		else parent[root_i] = parent[root_j];
	} else {
		parent[root_i] = parent[root_j];
		rnk[j]++;
	}
}

int construct(vvi p) {
	int N = (int) p.size(), numCCs = N;
	vector<int> parent(N), rnk(N, 0);
	for (int i = 0; i < N; i++)
		parent[i] = i;
	for (int i = 0; i < N; i++) {
		for (int j = i+1; j < N; j++) {
			if (p[i][j]) {
				if (p[i][j] == 3) {
					return 0;
				}
				merge(i, j, parent, rnk, numCCs);
			} else if (root(i, parent) == root(j, parent))
				return 0;
		}
	}

	unordered_map<int, int> roots;
	int c = 0;
	for (int i = 0; i < N; i++) {
		if (parent[i] == i)
			roots[i] = c++;
	}
	vvi CCs(numCCs, vi());
	for (int i = 0; i < N; i++)
		CCs[roots[root(i, parent)]].push_back(i);

	int CCsize, u, v, n, root_u, root_v;
	vi parentCC;
	vvi result(N, vi(N, 0)), oneTails;

	for (int i = 0; i < numCCs; i++) {
		CCsize = (int) CCs[i].size();
		n = CCsize;
		if (CCsize == 1) continue;
		parentCC = vi(CCsize);
		rnk.assign(CCsize, 0);
		for (int j = 0; j < CCsize; j++)
			parentCC[j] = j;
		for (int j = 0; j < CCsize; j++) {
			for (int k = j+1; k < CCsize; k++) {
				u = CCs[i][j];
				v = CCs[i][k];
				if (p[u][v] == 1)
					merge(u, v, parentCC, rnk, n);
				else if (root(u, parentCC) == root(v, parentCC))
					return 0;
			}
		}

		roots.clear();
		c = 0;
		for (int j = 0; j < CCsize; j++) {
			u = CCs[i][j];
			root_u = root(u, parentCC);
			if (root_u == j)
				roots[j] = c++;
			for (int k = j+1; k < CCsize; k++) {
				v = CCs[i][k];
				root_v = root(v, parentCC);
				if (root_u != root_v) {
					if (p[u][v] != 2) return 0;
				} else if (p[u][v] != 1) return 0;
			}
		}
		if (n == 2)
			return 0;
		oneTails = vvi(n, vi());
		for (int j = 0; j < CCsize; j++)
			oneTails[roots[root(CCs[i][j], parentCC)]].push_back(CCs[i][j]);

		for (int j = 0; j < n; j++) {
			for (int k = 0; k < (int) oneTails[j].size() - 1; k++)
				result[oneTails[j][k]][oneTails[j][k+1]] = result[oneTails[j][k+1]][oneTails[j][k]] = 1;
		}

		// oneTails formed and tails connected inside the tail as a snake
		for (int j = 0; j < n-1; j++)
			result[oneTails[j][0]][oneTails[j+1][0]] = result[oneTails[j+1][0]][oneTails[j][0]] = 1;

		if (n > 1)
			result[oneTails[0][0]][oneTails[n-1][0]] = result[oneTails[n-1][0]][oneTails[0][0]] = 1;
	}
	build(result);
	return 1;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 10
• Subtask 3: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4