Submission #779211

#	Time	Username	Problem	Language	Result	Execution time	Memory
779211		Elias	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	216 ms	22276 KiB

supertrees

#ifndef _DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif

#include <bits/stdc++.h>

using namespace std;

#ifdef _DEBUG
int construct(std::vector<std::vector<int>> p);
void build(std::vector<std::vector<int>> b);
#endif

#ifndef _DEBUG
#include <supertrees.h>
#endif

int construct(std::vector<std::vector<int>> p)
{
	int n = p.size();
	std::vector<std::vector<int>> answer(n, vector<int>(n));

	vector<int> all(n);
	for (int i = 0; i < n; i++)
		all[i] = i;

	auto split = [&](vector<int> a, int splitter)
	{
		int n = a.size();

		vector<set<int>> components;
		map<int, int> componentId;
		for (int i = 0; i < n; i++)
		{
			components.push_back({a[i]});
			componentId[a[i]] = i;
		}

		auto merge = [&](int a, int b)
		{
			a = componentId[a];
			b = componentId[b];

			assert(components[a].size() && components[b].size());

			if (a == b)
				return;

			if (components[a].size() < components[b].size())
				swap(a, b);

			for (auto x : components[b])
			{
				components[a].insert(x);
				componentId[x] = a;
			}

			components[b].clear();
		};

		for (int i = 0; i < n; i++)
			for (int j = i + 1; j < n; j++)
			{
				if (p[a[i]][a[j]] != splitter)
					merge(a[i], a[j]);
			}

		for (int i = 0; i < n; i++)
			for (int j = i + 1; j < n; j++)
			{
				if (p[a[i]][a[j]] == splitter && componentId[a[i]] == componentId[a[j]])
					return vector<set<int>>{};
			}

		components.erase(remove_if(components.begin(), components.end(), [](const set<int> &x)
								   { return x.size() == 0; }),
						 components.end());

		return components;
	};

	auto components = split(all, 0);

	if (components.size() == 0)
		return 0;

	for (auto component : components)
	{
		if (component.size() == 0)
			continue;

		vector<int> all_in_comp(component.begin(), component.end());

		set<int> values;

		for (int x : component)
			for (int y : component)
			{
				values.insert(p[x][y]);
			}

		if (values.count(3))
			return 0;

		bool threes = values.count(3);

		auto sub_components = split(all_in_comp, threes ? 3 : 2);

		if (sub_components.size() == 0 || sub_components.size() == 2 || (threes && sub_components.size() == 3))
			return 0;

		int prev_root = -1;
		int first_root = -1;
		int second_root = -1;
		for (auto sub_component : sub_components)
		{
			if (sub_component.size() == 0)
				continue;

			int prev = -1;
			for (auto x : sub_component)
			{
				if (prev != -1)
					answer[x][prev] = answer[prev][x] = 1;
				prev = x;
			}
			int x = *sub_component.begin();
			if (prev_root != -1)
				answer[x][prev_root] = answer[prev_root][x] = 1;
			else
				first_root = x;

			if (first_root != -1 && second_root == -1)
				second_root = x;

			prev_root = x;
		}
		if (first_root != -1 && first_root != prev_root)
			answer[first_root][prev_root] = answer[prev_root][first_root] = 1;

		if (prev_root != -1 && second_root != -1 && prev_root != second_root)
			answer[second_root][prev_root] = answer[prev_root][second_root] = 1;
	}

	build(answer);
	return 1;
}

#ifdef _DEBUG

#include <vector>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <string>

static int n;
static std::vector<std::vector<int>> p;
static std::vector<std::vector<int>> b;
static bool called = false;

static void check(bool cond, std::string message)
{
	if (!cond)
	{
		printf("%s\n", message.c_str());
		fclose(stdout);
		exit(0);
	}
}

void build(std::vector<std::vector<int>> _b)
{
	check(!called, "build is called more than once");
	called = true;
	check((int)_b.size() == n, "Invalid number of rows in b");
	for (int i = 0; i < n; i++)
	{
		check((int)_b[i].size() == n, "Invalid number of columns in b");
	}
	b = _b;
}

int main()
{
	// freopen("3-21.in", "r", stdin);

	assert(scanf("%d", &n) == 1);

	p.resize(n);
	for (int i = 0; i < n; i++)
	{
		p[i].resize(n);
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			assert(scanf("%d", &p[i][j]) == 1);
		}
	}
	fclose(stdin);

	int possible = construct(p);

	check(possible == 0 || possible == 1, "Invalid return value of construct");
	if (possible == 1)
	{
		check(called, "construct returned 1 without calling build");
	}
	else
	{
		check(!called, "construct called build but returned 0");
	}

	printf("%d\n", possible);
	if (possible == 1)
	{
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (j)
				{
					printf(" ");
				}
				printf("%d", b[i][j]);
			}
			printf("\n");
		}
	}
	fclose(stdout);
}

#endif

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