Submission #314162

#	Time	Username	Problem	Language	Result	Execution time	Memory
314162		luisoncpp	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	266 ms	22392 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <cassert>
#include <iostream>
#include <optional>

using std::cout;
using std::endl;

using Matriz = std::vector<std::vector<int>>;
using Comp = std::unordered_set<int>;
using Rama = std::unordered_set<int>;

void ConstruyeLista(const Comp& comp, Matriz& matriz) {
	int prev = -1;
	for (int actual : comp) {
		if (prev != -1) {
			matriz[prev][actual] = 1;
			matriz[actual][prev] = 1;
		}
		prev = actual;
	}
}
bool ConstruyeCiclo(const std::vector<int>& vertices, Matriz& matriz) {
	int n = vertices.size();
	if (n < 3) {
		return false;
	}
	for (int i = 0; i < n; ++i) {
		int a = vertices[i];
		int b = vertices[(i+1)%n];
		matriz[a][b] = 1;
		matriz[b][a] = 1;
	}
	return true;
}

bool Contiene(const Comp& c, int v) {
	return c.count(v) > 0;
}

struct Componentes {
	Componentes(int n) :	n(n), comp_id(n, -1) {}
	std::vector<Comp> comps;
	int n;
	std::vector<int> comp_id;
	void AgregaComponente(Comp c) {
		for (int v : c) {
			comp_id[v] = comps.size();
		}
		comps.push_back(std::move(c));
	}
};

std::optional<Componentes> EncuentraComponentesConexas(const Matriz& caminos) {
	int n = caminos.size();
	Componentes ret(n);
	for (int origen = 0; origen < n; ++origen) {
		int comp_id = ret.comp_id[origen];
		if (comp_id == -1) {
			Comp comp;
			for (int dest = 0; dest < n; ++dest) {
				if (caminos[origen][dest] > 0) {
					comp.insert(dest);
				}
			}
			ret.AgregaComponente(std::move(comp));
		} else {
			auto& comp = ret.comps[comp_id];
			for (int dest = 0; dest < n; ++dest) {
				if ((caminos[origen][dest] > 0) != Contiene(comp, dest)){
					return std::nullopt;
				}
			}
		}
	}
	return ret;
}

std::optional<Componentes> EncuentraRamas(const Matriz& caminos, Comp& comp) {
	int n = caminos.size();
	Componentes ret(n);
	for (int origen : comp) {
		int comp_id = ret.comp_id[origen];
		if (comp_id == -1) {
			Comp rama;
			for (int dest : comp) {
				if (caminos[origen][dest] == 1) {
					rama.insert(dest);
				}
			}
			ret.AgregaComponente(std::move(rama));
		} else {
			auto& rama = ret.comps[comp_id];
			for (int dest : comp) {
				if ((caminos[origen][dest] == 1) != Contiene(rama, dest)){
					return std::nullopt;
				}
			}
		}
	}
	return ret;
}

bool Busca(const Matriz& matriz, int a) {
	for (const auto& vec : matriz) {
		for (int val : vec) {
			if (val == a) {
				return true;
			}
		}
	}
	return false;
}

int construct(std::vector<std::vector<int>> caminos) {
	int n = caminos.size();
	if (Busca(caminos, 3)) {
		return 0;
	}
	auto conectividad = EncuentraComponentesConexas(caminos);
	if (!conectividad) {
		return 0;
	}
	Matriz answer(n, std::vector<int>(n, 0));
	for (auto& c: conectividad->comps) {
		auto ramas = EncuentraRamas(caminos, c);
		if (!ramas) {
			return 0;
		}
		std::vector<int> vertices_ciclo;
		for (auto& rama : ramas->comps) {
			assert(rama.size() > 0);
			ConstruyeLista(rama, answer);
			vertices_ciclo.push_back(*rama.begin());
		}
		if (vertices_ciclo.size() > 1 && !ConstruyeCiclo(vertices_ciclo, answer)) {
			return 0;
		}
	}
	build(answer);
	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