Submission #779417

#	Time	Username	Problem	Language	Result	Execution time	Memory
779417		Josia	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	226 ms	24276 KiB

supertrees

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

using namespace std;




struct uf {
	vector<int> chefs;
	uf (int n) {
		chefs.resize(n);
		for (int i = 0; i<n; i++) chefs[i] = i;
	}

	int find(int x) {
		if (chefs[x] == x) return x;
		return chefs[x] = find(chefs[x]);
	}

	void unite(int a, int b) {
		a = find(a);
		b = find(b);

		chefs[a] = b;
	}
};





int construct(std::vector<std::vector<int>> p) {
	for (auto i: p) {
		for (auto j: i) if (j == 3) return 0;
	}

	int n = p.size();
	if (n == 1) {
		if (p[0][0] == 1) {
			build({{0}});
			return 1;
		}
		return 0;
	}

	// ----
	uf u(n);

	for (int i = 0; i<n; i++) {
		for (int j = 0; j<n; j++) {
			if (p[i][j]) u.unite(i, j);
		}
	}

	for (int i = 0; i<n; i++) {
		for (int j = 0; j<n; j++) {
			if ((bool)(p[i][j]) != (u.find(i) == u.find(j))) return 0;
		}
	}

	vector<vector<int>> vals(n);

	for (int i = 0; i<n; i++) {
		for (int j = 0; j<n; j++) {
			if (u.find(j) == i) vals[i].push_back(j);
		}
	}
	// ----


	uf u2(n);

	for (int i = 0; i<n; i++) {
		for (int j = 0; j<n; j++) {
			if (p[i][j]==1) u2.unite(i, j);
		}
	}

	for (int i = 0; i<n; i++) {
		for (int j = 0; j<n; j++) {
			if ((p[i][j]==1) != (u2.find(i) == u2.find(j))) return 0;
		}
	}

	vector<vector<int>> vals2(n);

	for (int i = 0; i<n; i++) {
		for (int j = 0; j<n; j++) {
			if (u2.find(j) == i) vals2[i].push_back(j);
		}
	}



	vector<vector<int>> secondConnect(n);

	vector<vector<int>> answer(n, vector<int>(n));

	for (auto v: vals2) {
		if (v.size()) secondConnect[u.find(v[0])].push_back(u2.find(v[0]));
		for (int i = 0; i<(int)(v.size())-1; i++) {
			answer[v[i]][v[(i+1)%v.size()]] = 1;
			answer[v[(i+1)%v.size()]][v[i]] = 1;
		}
	}

	for (auto v: secondConnect) {
		if (v.size() == 1) continue;
		if (v.size() == 2) return 0;
 
		for (int i = 0; i<(int)(v.size()); i++) {
			answer[v[i]][v[(i+1)%v.size()]] = 1;
			answer[v[(i+1)%v.size()]][v[i]] = 1;
		}
 
	}

	build(answer);
	return 1;
}

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