Submission #1149028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149028		blackslex	Connecting Supertrees (IOI20_supertrees)	C++20	0 / 100	0 ms	328 KiB

supertrees

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

using namespace std;

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> answer(n, vector<int>(n));
	vector<int> par(n); iota(par.begin(), par.end(), 0);
	function<int(int)> fset = [&] (int x) {return (par[x] == x ? x : par[x] = fset(par[x]));};
	auto mg = [&] (int x, int y) {
		if ((x = fset(x)) == (y = fset(y))) return;
		par[y] = x;
	};
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (p[i][j]) mg(i, j);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (fset(i) == fset(j) && p[i][j] != 2) return 0;
		}
	}
	for (int i = 0; i < n; i++) {
		if (fset(i) != i) continue;
		vector<int> c;
		for (int j = 0; j < n; j++) {
			if (fset(j) == i) c.emplace_back(j);
		}
		int csz = c.size();
		for (int j = 0; j < csz; j++) {
			answer[c[j]][c[(j + 1) % csz]] = answer[c[(j + 1) % csz]][c[j]] = 1;
		}
		for (int j = 0; j < csz; j++) {
			for (int k = 0; k < csz; k++) {
				if (p[c[j]][c[k]] != 2) return 0;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		answer[i][i] = 0;
	}
	build(answer);
	return 1;
}

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