Submission #300198

#	Time	Username	Problem	Language	Result	Execution time	Memory
300198		VladaMG98	Connecting Supertrees (IOI20_supertrees)	C++17	19 / 100	259 ms	22360 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

struct dsu {
	int n;
	vector<int> parent, rank;
	dsu(int _n) {
		n = _n;
		parent.resize(n);
		rank.resize(n);
		for (int i = 0; i < n; i++) {
			parent[i] = i;
			rank[i] = 1;
		}
	}
	int get(int x) {
		if (parent[x] == x) return x;
		return parent[x] = get(parent[x]);
	}
	bool unite(int x, int y) {
		x = get(x), y = get(y);
		if (x == y) return false;
		if (rank[x] < rank[y]) swap(x, y);
		parent[y] = x;
		rank[x] += rank[y];
		return true;
	}
	vector<int> all_roots() {
		set<int> s;
		for (int i = 0; i < n; i++) s.insert(get(i));
		vector<int> res;
		for (auto &x : s) res.push_back(x);
		return res;
	}
};

void path(vector<vector<int>> &answer, vector<int> nodes) {
	if (nodes.size() == 1) return;
	for (int i = 1; i < (int)nodes.size(); i++) {
		answer[nodes[i - 1]][nodes[i]] = 1;
		answer[nodes[i]][nodes[i - 1]] = 1;
	}
}

void cycle(vector<vector<int>> &answer, vector<int> nodes) {
	if (nodes.size() == 1) return;
	path(answer, nodes);
	answer[nodes.back()][nodes[0]] = 1;
	answer[nodes[0]][nodes.back()] = 1;

}
int construct(vector<std::vector<int>> p) {
	int n = p.size();
	vector<vector<int>> answer;
	answer.resize(n);
	for (int i = 0; i < n; i++) {
		answer[i].resize(n);
		for (int j = 0; j < n; j++) {
			answer[i][j] = 0;
		}
	}
	dsu d(n);
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (p[i][j] != p[j][i]) return 0;
			if (p[i][j] > 0) d.unite(i, j);
		}
	}
	vector<int> roots = d.all_roots();
	int roots_num = (int)roots.size();
	unordered_map<int, int> ind;
	for (int i = 0; i < roots_num; i++) {
		ind[roots[i]] = i;
	}
	vector<vector<int>> parts(roots_num);
	for (int i = 0; i < n; i++) {
		parts[ind[d.get(i)]].push_back(i);
	}
	for (int i = 0; i < roots_num; i++) {
		vector<int> &cur = parts[i];
		if (cur.size() == 2) return 0;
		int small_sz = (int)cur.size();
		for (	int j = 0; j < small_sz; j++) {
			for (int k = 0; k < small_sz; k++) {
				if (p[cur[j]][cur[k]] == 0) return 0;
			}
		}
		cycle(answer, cur);
	}
	build(answer);
	return 1;
}

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