Submission #1032847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032847		fv3	Connecting Supertrees (IOI20_supertrees)	C++14	19 / 100	148 ms	28116 KiB

supertrees

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

using namespace std;

int construct(vector<vector<int>> p) 
{
	int n = p.size();

	// Subtask 2: line
	// Subtask 3: circles
	// Subtask 5: 0, 1, 2

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (p[i][j])
				p[i][j] = 2;
		}
	}

	for (int i = 0; i < n; i++)
		p[i].push_back(i);
	sort(p.begin(), p.end());

	int l = 0, r = 1;
	vector<vector<int>> answer(n, vector<int>(n));
	while (r < n)
	{
		int i = 0;
		for (; i < n; i++)
		{
			if (p[r][i] != p[r-1][i])
				break;
		}

		if (i == n)
		{
			answer[p[r-1].back()][p[r].back()] = 1;
			answer[p[r].back()][p[r-1].back()] = 1;
		}
		else
		{
			int sz = 0;
			for (int j = 0; j < n; j++)
			{
				if (p[r-1][j])
					sz++;
			}

			if (r - l != sz || r - l == 2)
				return 0;

			if (r - l > 2)
			{	
				answer[p[r-1].back()][p[l].back()] = 1;
				answer[p[l].back()][p[r-1].back()] = 1;
			}

			l = r;
		}

		r++;
	}
	if (l < n - 1)
	{
		int sz = 0;
		for (int j = 0; j < n; j++)
		{
			if (p[r-1][j])
				sz++;
		}

		if (r - l != sz || r - l == 2)
			return 0;

		if (r - l > 2)
		{	
			answer[p[r-1].back()][p[l].back()] = 1;
			answer[p[l].back()][p[r-1].back()] = 1;
		}	
	}
	

	build(answer);

	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