Submission #1279007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279007		IBory	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	130 ms	26160 KiB

supertrees

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

const int MAX = 1004;
vector<int> A[MAX], B[MAX];

struct UF {
	int R[MAX];
	UF() {
		iota(R, R + MAX, 0);
	}
	int Find(int n) {
		if (n == R[n]) return n;
		return R[n] = Find(R[n]);
	}
	void Union(int a, int b) {
		a = Find(a), b = Find(b);
		if (a == b) return;
		R[a] = b;
	}
} UF1, UF2;

int construct(vector<vector<int>> P) {
	int N = P.size();
	for (auto& v : P) for (int n : v) if (n == 3) return 0;

	for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) {
		if (P[i][j]) UF2.Union(i, j);
		if (P[i][j] == 1) UF1.Union(i, j);
	}

	bool ok = 1;
	for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) {
		if (UF2.Find(i) != UF2.Find(j)) ok &= (P[i][j] == 0);
		else if (UF1.Find(i) != UF1.Find(j)) {
			ok &= (P[i][j] == 2);
			B[UF2.Find(i)].push_back(UF1.Find(j));
		}
		else {
			ok &= (P[i][j] == 1);
			A[UF1.Find(i)].push_back(j);
		}
	}
	if (!ok) return 0;

	for (int i = 0; i < N; ++i) {
		sort(A[i].begin(), A[i].end());
		A[i].erase(unique(A[i].begin(), A[i].end()), A[i].end());
		sort(B[i].begin(), B[i].end());
		B[i].erase(unique(B[i].begin(), B[i].end()), B[i].end());
	}

	vector<vector<int>> G(N, vector<int>(N, 0));
	for (int i = 0; i < N; ++i) {
		for (int n : A[i]) G[i][n] = G[n][i] = 1;
		if (B[i].empty()) continue;
		if (B[i].size() == 2) return 0;
		B[i].push_back(i);
		for (int j = 0; j < B[i].size(); ++j) {
			int a = B[i][j], b = B[i][(j + 1) % B[i].size()];
			G[a][b] = G[b][a] = 1;
		}
	}
	for (int i = 0; i < N; ++i) G[i][i] = 0;

	build(G);
	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