Submission #366933

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

supertrees

#include <iostream>
#include <vector>
#include <unordered_map>
#include "supertrees.h"
using namespace std;

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

void unirConjuntos(int a, int b, vector<int> & padre, vector<int> & alturaAprox, int & numeroConjuntos) {
    int raiz_a, raiz_b;
    raiz_a = raiz(a, padre);
    raiz_b = raiz(b, padre);
    if (raiz_a == raiz_b) return;
    numeroConjuntos--;
    if (alturaAprox[raiz_a] > alturaAprox[raiz_b]) {
        padre[raiz_b] = raiz_a;
    } else if (alturaAprox[raiz_b] > alturaAprox[raiz_a]) {
        padre[raiz_a] = raiz_b;
    } else {
        padre[raiz_a] = raiz_b;
        alturaAprox[raiz_b]++;
    }
}

int construct(vector<vector<int>> p) {
	int N = (int) p.size(), numCCs = N;
	vector<int> padre(N), alturaAprox(N, 0);

	for (int i = 0; i < N; i++)
		padre[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;
				}
				unirConjuntos(i, j, padre, alturaAprox, numCCs);
			} else if (raiz(i, padre) == raiz(j, padre))
				return 0;
		}
	}
	unordered_map<int, int> roots;
	int c = 0;
	for (int i = 0; i < N; i++) {
		if (padre[i] == i)
			roots[i] = c++;
	}

	vector<vector<int>> CCs(numCCs);
	for (int i = 0; i < N; i++)
		CCs[roots[raiz(i, padre)]].push_back(i);

	int CCsize, u, v, n, root_u, root_v;

	vector<vector<int>> result(N, vector<int>(N, 0)), oneTails;

	for (int i = 0; i < numCCs; i++) {
		CCsize = (int) CCs[i].size();
		if (CCsize == 1) continue;

		// encontramos las "serpientes" de esta componente conexa
		n = CCsize;
		for (auto node: CCs[i]) {
			padre[node] = node;
			alturaAprox[node] = 0;
		}
		for (int j = 0; j < CCsize; j++) {
			u = CCs[i][j];
			root_u = raiz(u, padre);
			for (int k = j+1; k < CCsize; k++) {
				v = CCs[i][k];
				if (p[u][v] == 1)
					unirConjuntos(u, v, padre, alturaAprox, n);
				else if (root_u == raiz(v, padre))
					return 0;
			}
		}

		// nos aseguramos de que no hay incongruencias en esta componente conexa
		if (n == 2) return 0;

		roots.clear();
		c = 0;
		for (int j = 0; j < CCsize; j++) {
			u = CCs[i][j];
			root_u = raiz(u, padre);
			if (root_u == u)
				roots[u] = c++;
			for (int k = j+1; k < CCsize; k++) {
				v = CCs[i][k];
				root_v = raiz(v, padre);
				if (root_u != root_v) {
					if (p[u][v] != 2) {
						return 0;
					}
				} else if (p[u][v] != 1) {
					return 0;
				}
			}
		}
		// conectar los elementos dentro de una serpiente
		oneTails = vector<vector<int>>(n);
		for (int j = 0; j < CCsize; j++)
			oneTails[roots[raiz(CCs[i][j], padre)]].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;
		}

		// conectar el ciclo de cabezas de serpiente
		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: 10 / 10
• Subtask 3: 19 / 19
• Subtask 4: 35 / 35
• Subtask 5: 21 / 21
• Subtask 6: 4 / 4