Submission #366934

#	Time	Username	Problem	Language	Result	Execution time	Memory
366934		BlancaHM	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	270 ms	22380 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;

	// encontramos las componentes conexas
	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;
		}
	}

	// damos un índice a cada raíz
	unordered_map<int, int> raices;
	int c = 0;
	for (int i = 0; i < N; i++) {
		if (padre[i] == i)
			raices[i] = c++;
	}

	// guardamos las componentes conexas
	vector<vector<int>> CCs(numCCs);
	for (int i = 0; i < N; i++)
		CCs[raices[raiz(i, padre)]].push_back(i);

	int CCtamano, u, v, n, raiz_u, raiz_v;

	vector<vector<int>> resultadoFinal(N, vector<int>(N, 0)), serpientes;

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

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

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

		raices.clear();
		c = 0;
		for (int j = 0; j < CCtamano; j++) {
			u = CCs[i][j];
			raiz_u = raiz(u, padre);
			if (raiz_u == u)
				raices[u] = c++;
			for (int k = j+1; k < CCtamano; k++) {
				v = CCs[i][k];
				raiz_v = raiz(v, padre);
				if (raiz_u != raiz_v) {
					if (p[u][v] != 2) {
						return 0;
					}
				} else if (p[u][v] != 1) {
					return 0;
				}
			}
		}

		// conectamos los elementos dentro de una serpiente
		serpientes = vector<vector<int>>(n);
		for (int j = 0; j < CCtamano; j++)
			serpientes[raices[raiz(CCs[i][j], padre)]].push_back(CCs[i][j]);
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < (int) serpientes[j].size() - 1; k++)
				resultadoFinal[serpientes[j][k]][serpientes[j][k+1]] = resultadoFinal[serpientes[j][k+1]][serpientes[j][k]] = 1;
		}

		// conectamos el ciclo de cabezas de serpiente
		for (int j = 0; j < n-1; j++)
			resultadoFinal[serpientes[j][0]][serpientes[j+1][0]] = resultadoFinal[serpientes[j+1][0]][serpientes[j][0]] = 1;

		if (n > 1)
			resultadoFinal[serpientes[0][0]][serpientes[n-1][0]] = resultadoFinal[serpientes[n-1][0]][serpientes[0][0]] = 1;
	}
	build(resultadoFinal);
	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