Submission #1149052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149052		blackslex	Connecting Supertrees (IOI20_supertrees)	C++20	46 / 100	131 ms	22188 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));
	auto add = [&] (int x, int y) {
		answer[x][y] = answer[y][x] = 1;
	};
	vector<int> par(n), par2(n);
	iota(par.begin(), par.end(), 0);
	iota(par2.begin(), par2.end(), 0);
	function<int(int)> fset = [&] (int x) {return (par[x] == x ? x : par[x] = fset(par[x]));};
	function<int(int)> fset2 = [&] (int x) {return (par2[x] == x ? x : par2[x] = fset2(par2[x]));};
	auto mg = [&] (int x, int y) {
		if ((x = fset(x)) == (y = fset(y))) return;
		par[y] = x;
	};
	auto mg2 = [&] (int x, int y) {
		if ((x = fset2(x)) == (y = fset2(y))) return;
		par2[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++) {
		if (fset(i) != i) continue;
		vector<int> c, cc;
		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++) {
			for (int k = 0; k < csz; k++) {
				if (c[j] != c[k] && p[c[j]][c[k]] == 1) mg2(c[j], c[k]);
			}
		}
		for (int j = 0; j < csz; j++) {
			if (fset2(c[j]) != c[j]) continue;
			cc.emplace_back(c[j]);
			vector<int> c2;
			for (int k = 0; k < csz; k++) {
				if (fset2(c[k]) == c[j]) c2.emplace_back(c[k]);
			}
			int csz2 = c2.size();
			for (int k = 0; k < csz2 - 1; k++) {
				add(c2[k], c2[k + 1]);
			}
		}
		sort(cc.begin(), cc.end()); cc.resize(unique(cc.begin(), cc.end()) - cc.begin());
		int ccsz = cc.size();
		for (int j = 0; j < ccsz; j++) {
			add(cc[j], cc[(j + 1) % ccsz]);
		}
	}
	for (int i = 0; i < n; i++) {
		answer[i][i] = 0;
	}
	build(answer);
	return 1;
}

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