Submission #1229501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229501		kargneq	Connecting Supertrees (IOI20_supertrees)	C++20	21 / 100	118 ms	22276 KiB

supertrees

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

using namespace std;


struct DSU {
	vector<int> p, sz;
	DSU(int n = 0) : p(n), sz(n, 1) { iota(p.begin(), p.end(), 0); }
	int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
	void merge(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b) return;
		if (sz[a] < sz[b]) swap(a, b);
		p[b] = a;
		sz[a] += sz[b];
	}
};

int construct(vector<vector<int>> p) {
	int n = (int)p.size();
	DSU dsu(n);

	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++)
			if (p[i][j] == 1) dsu.merge(i, j);

	for (int i = 0; i < n; i++)
		for (int j = i + 1; j < n; j++) {
			bool same = (dsu.find(i) == dsu.find(j));
			if ((p[i][j] == 0 && same) || (p[i][j] == 1 && !same)) return 0;
		}

	vector<vector<int>> b(n, vector<int>(n, 0));
	unordered_map<int, vector<int>> buckets;
	for (int v = 0; v < n; ++v) buckets[dsu.find(v)].push_back(v);

	for (auto& kv : buckets) {
		const vector<int>& v = kv.second;
		for (size_t k = 1; k < v.size(); ++k) {
			int u = v[0], w = v[k];
			b[u][w] = b[w][u] = 1;
		}
	}

	build(b);
	return 1;
}

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