Submission #426101

#	Time	Username	Problem	Language	Result	Execution time	Memory
426101		erekle	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	312 ms	47664 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>

using namespace std;

// DSU
int root(int i, vector<int> &parent) {
	return parent[i] < 0 ? i : (parent[i] = root(parent[i], parent));
}
bool unite(int i, int j, vector<int> &parent) {
	i = root(i, parent), j = root(j, parent);
	if (i == j) return false;
	if (parent[i] < parent[j]) swap(i, j);
	parent[j] += parent[i];
	parent[i] = j;
	return true;
}

int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> answer(n, vector<int>(n));
	
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (p[i][j] == 3) return 0;
		}
	}

	vector<int> parent(n, -1);
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (p[i][j]) unite(i, j, parent);
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (!p[i][j] && root(i, parent) == root(j, parent)) return 0;
		}
	}

	vector<int> parent2(n, -1);
	// now within components
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (root(i, parent) != root(j, parent)) continue;
			if (p[i][j] == 1) unite(i, j, parent2);
		}
	}

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (root(i, parent2) == root(j, parent2) && p[i][j] != 1) return 0;
		}
	}

	auto connect = [&](int i, int j) {answer[i][j] = answer[j][i] = 1;};
	
	vector<vector<vector<int>>> g(n, vector<vector<int>>(n));
	for (int i = 0; i < n; ++i) { // chains
		int x = root(i, parent), y = root(i, parent2);
		if (!g[x][y].empty()) connect(g[x][y].back(), i);
		g[x][y].push_back(i);
	}

	for (int x = 0; x < n; ++x) { // cycle using endpoints of chains
		vector<int> ys;
		for (int y = 0; y < n; ++y) {
			if (!g[x][y].empty()) ys.push_back(y);
		}
		int m = ys.size();
		if (m <= 1) continue;
		for (int i = 0; i < m; ++i) connect(g[x][ys[i]][0], g[x][ys[(i+1)%m]][0]);
	}

	build(answer);
	return 1;
}

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