Submission #1229502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229502		kargneq	Connecting Supertrees (IOI20_supertrees)	C++20	19 / 100	118 ms	22152 KiB

supertrees

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

using namespace std;

struct DSU {
	vector<int> p, sz;
	DSU(int n) : p(n, -1), sz(n, 1) {}
	int find(int v) { return p[v] == -1 ? v : p[v] = find(p[v]); }
	void unite(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++) {
		if (p[i][i] != 1) return 0;
		for (int j = 0; j < n; j++) {
			if (p[i][j] != p[j][i]) return 0;
			if (i != j && p[i][j] == 1) return 0;
		}
	}

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

	for (int i = 0; i < n; ++i)
		for (int j = i + 1; j < n; ++j)
			if (dsu.find(i) == dsu.find(j) && p[i][j] != 2) return 0;

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

	vector<pair<int, int>> edges;

	for (auto& kv : comp) {
		const vector<int>& g = kv.second;
		int k = (int)g.size();

		if (k == 2) return 0;
		if (k <= 1) continue;

		for (int i = 0; i < k; i++) {
			int u = g[i], v = g[(i + 1) % k];
			edges.push_back({u, v});
		}
	}
	vector<vector<int>> b(n, vector<int>(n, 0));
	for (auto e : edges) {
		b[e.first][e.second] = b[e.second][e.first] = 1;
	}
	build(b);
	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