Submission #314160

#	Time	Username	Problem	Language	Result	Execution time	Memory
314160		luisoncpp	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	270 ms	22264 KiB

supertrees

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

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

using Matriz = std::vector<std::vector<int>>;
using Comp = 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 Contiene(const Comp& c, int v) {
	return c.count(v) > 0;
}

struct ComponentesConexas {
	ComponentesConexas(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<ComponentesConexas> EncuentraComponentesConexas(const Matriz& caminos) {
	int n = caminos.size();
	ComponentesConexas 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;
}

int construct(std::vector<std::vector<int>> caminos) {
	int n = caminos.size();
	auto comps = EncuentraComponentesConexas(caminos);
	if (!comps) {
		return 0;
	}
	Matriz answer(n, std::vector<int>(n, 0));
	for (auto& c: comps->comps) {
		ConstruyeLista(c, answer);
	}
	build(answer);
	return 1;
}

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