Submission #452055

#	Time	Username	Problem	Language	Result	Execution time	Memory
452055		rainboy	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	330 ms	22480 KiB

supertrees

#include "supertrees.h"
#include <string.h>

using namespace std;

typedef vector<int> vi;

const int N = 1000;

int abs_(int a) { return a > 0 ? a : -a; }

int ds[N];

int find(int i) {
	return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}

void join(int i, int j) {
	i = find(i);
	j = find(j);
	if (i == j)
		return;
	if (ds[i] > ds[j])
		ds[i] = j;
	else {
		if (ds[i] == ds[j])
			ds[i]--;
		ds[j] = i;
	}
}

char root[N];

int construct(vector<vi> pp) {
	int n = pp.size(), i, j, k;
	vector<vi> aa(n);

	for (i = 0; i < n; i++)
		for (j = i + 1; j < n; j++)
			if (pp[i][j] == 3)
				return 0;
	for (i = 0; i < n; i++)
		aa[i].resize(n);
	memset(ds, -1, n * sizeof *ds);
	for (i = 0; i < n; i++)
		for (j = i + 1; j < n; j++)
			if (pp[i][j] == 1)
				join(i, j);
	for (i = 0; i < n; i++)
		for (j = i + 1; j < n; j++)
			if ((find(i) == find(j)) != (pp[i][j] == 1))
				return 0;
	for (i = 0; i < n; i++)
		if ((j = find(i)) != i)
			aa[i][j] = aa[j][i] = 1;
		else
			root[i] = 1;
	for (i = 0; i < n; i++)
		for (j = i + 1; j < n; j++)
			if (pp[i][j] == 2)
				join(i, j);
	for (i = 0; i < n; i++)
		for (j = i + 1; j < n; j++)
			if ((find(i) == find(j)) != (pp[i][j] != 0))
				return 0;
	for (i = 0; i < n; i++)
		if (root[i]) {
			int c;

			root[i] = 0;
			k = i, c = 1;
			for (j = 0; j < n; j++)
				if (root[j] && find(j) == find(i))
					root[j] = 0, aa[j][k] = aa[k][j] = 1, k = j, c++;
			if (c == 2)
				return 0;
			if (k != i)
				aa[i][k] = aa[k][i] = 1, k = j;
		}
	build(aa);
	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