Submission #351284

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

	vi allTwos, rest;
	vvi result(N, vi(N, 0));
	int con;
	bool twos;
	for (int i = 0; i < numCCs; i++) {
		if ((int) CCs[i].size() == 1) continue;
		allTwos.clear();
		rest.clear();
		for (int j = 0; j < (int) CCs[i].size(); j++) {
			twos = true;
			for (int k = 0; k < (int) CCs[i].size(); k++) {
				if (k == j) continue;
				con = p[CCs[i][j]][CCs[i][k]];
				if (con == 1)
					twos = false;
				else if (con == 0)
					return 0;
			}
			if (twos) allTwos.push_back(CCs[i][j]);
			else rest.push_back(CCs[i][j]);
		}
		for (int i = 0; i < (int) allTwos.size()-1; i++)
			result[allTwos[i]][allTwos[i+1]] = result[allTwos[i+1]][allTwos[i]] = 1;
		for (int i = 0; i < (int) rest.size()-1; i++)
			result[rest[i]][rest[i+1]] = result[rest[i+1]][rest[i]] = 1;
		if ((int) allTwos.size() == 1) return 0;
		if (rest.empty())
			result[allTwos[0]][allTwos[(int) allTwos.size()-1]] = result[allTwos[(int) allTwos.size()-1]][allTwos[0]] = 1;
		else if (allTwos.size())
			result[allTwos[0]][rest[0]] = result[rest[0]][allTwos[0]] = result[rest[0]][allTwos[(int) allTwos.size()-1]] = result[allTwos[(int) allTwos.size()-1]][rest[0]] = 1;
	}
	build(result);
	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