Submission #516709

#	Time	Username	Problem	Language	Result	Execution time	Memory
516709		pavement	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	211 ms	24316 KiB

supertrees

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

#define pb push_back

int link[1005], sz[1005], link2[1005], sz2[1005];
vector<int> vec[1005], vec2[1005];

int find(int x) {
	if (x == link[x]) return x;
	return link[x] = find(link[x]);
}

void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	if (sz[b] > sz[a]) swap(a, b);
	sz[a] += sz[b];
	for (int i : vec[b]) vec[a].pb(i);
	link[b] = a;
}

int find2(int x) {
	if (x == link2[x]) return x;
	return link2[x] = find2(link2[x]);
}

void unite2(int a, int b) {
	a = find2(a);
	b = find2(b);
	if (a == b) return;
	if (sz2[b] > sz2[a]) swap(a, b);
	sz2[a] += sz2[b];
	for (int i : vec2[b]) vec2[a].pb(i);
	link2[b] = link2[a];
}

int construct(vector<vector<int> > p) {
	int n = p.size();
	vector<vector<int> > b(n, vector<int>(n, 0));
	for (int i = 0; i < n; i++) {
		link[i] = i;
		sz[i] = 1;
		link2[i] = i;
		sz2[i] = 1;
		vec[i].pb(i);
		vec2[i].pb(i);
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (p[i][j] == 1) unite(i, j);
			else if (p[i][j] == 3) return 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (p[i][j] == 2) unite2(find(i), find(j));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (p[i][j] == 0 && find2(find(i)) == find2(find(j))) return 0;
			else if (p[i][j] == 1 && find(i) != find(j)) return 0;
			else if (p[i][j] == 2 && (find2(find(i)) != find2(find(j)) || find(i) == find(j))) return 0;
	for (int i = 0; i < n; i++)
		if (i == find(i) && i == find2(i)) {
			if (vec2[i].size() == 2) return 0;
			else if (vec2[i].size() == 1) {
				for (int j = 0; j < (int)vec[i].size() - 1; j++)
					b[vec[i][j]][vec[i][j + 1]] = b[vec[i][j + 1]][vec[i][j]] = 1;
			} else {
				for (int j : vec2[i])
					for (int k = 0; k < (int)vec[j].size() - 1; k++)
						b[vec[j][k]][vec[j][k + 1]] = b[vec[j][k + 1]][vec[j][k]] = 1;
				for (int j = 0; j < (int)vec2[i].size() - 1; j++)
					b[vec2[i][j]][vec2[i][j + 1]] = b[vec2[i][j + 1]][vec2[i][j]] = 1;
				b[vec2[i][0]][vec2[i].back()] = b[vec2[i].back()][vec2[i][0]] = 1;
			}
		}
	build(b);
	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