Submission #1032921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032921		fv3	Connecting Supertrees (IOI20_supertrees)	C++14	56 / 100	140 ms	32004 KiB

supertrees

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

using namespace std;

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

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

	// 1. Find all parts which are the same
	vector<vector<int>> parts = { {p[0].back()} };
	map<vector<int>, vector<pair<int, int>>> cycles;

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

		if (i != n)
		{
			parts.push_back({p[r].back()});

			// Count 1's in last part
			int one_cnt = 0;
			for (int j = 0; j < n; j++)
			{
				if (p[r-1][j] == 1)
					one_cnt++;
			}

			if (one_cnt != r - l)
				return 0;

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

			cycles[bs].push_back({p[r-1].back(), parts[parts.size()-2].size()});
			l = r;
		}
		else
		{
			parts.back().push_back(p[r].back());
		}

		r++;
	}

	// Count 1's in last part
	int one_cnt = 0;
	for (int j = 0; j < n; j++)
	{
		if (p[r-1][j] == 1)
			one_cnt++;
	}

	if (one_cnt != r - l)
		return 0;

	vector<int> bs(n);
	for (int j = 0; j < n; j++)
	{
		if (p[r-1][j]) 
			bs[j] = 1;
	}
	cycles[bs].push_back({p[r-1].back(), parts[parts.size()-1].size()});

	// 2. Generate parts
	vector<vector<int>> answer(n, vector<int>(n));
	for (auto path : parts)
	{
		for (int i = 1; i < path.size(); i++)
		{
			answer[path[i]][path[i-1]] = 1;
			answer[path[i-1]][path[i]] = 1;
		}
	}

	// 3. Generate cycles
	for (auto cycle : cycles)
	{
		if (cycle.second.size() == 1)
			continue;

		if (cycle.second.size() == 2)
			return 0;

		int cyclesize = 0;
		for (auto e : cycle.first)
			if (e) cyclesize++;

		int realsize = 0;
		for (auto e : cycle.second)
		{
			realsize += e.second;
		}

		if (cyclesize != realsize)
			return 0;

		for (auto e : cycle.second)
			cerr << e.first << ' ';
		cerr << '\n';

		for (int i = 1; i < cycle.second.size(); i++)
		{
			answer[cycle.second[i].first][cycle.second[i-1].first] = 1;
			answer[cycle.second[i-1].first][cycle.second[i].first] = 1;
		}
		answer[cycle.second[0].first][cycle.second.back().first] = 1;
		answer[cycle.second.back().first][cycle.second[0].first] = 1;
	}

	// 4. Profit
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:84:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for (int i = 1; i < path.size(); i++)
      |                   ~~^~~~~~~~~~~~~
supertrees.cpp:117:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |   for (int i = 1; i < cycle.second.size(); i++)
      |                   ~~^~~~~~~~~~~~~~~~~~~~~

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