Submission #386011

#	Time	Username	Problem	Language	Result	Execution time	Memory
386011		AdOjis485	Connecting Supertrees (IOI20_supertrees)	C++14	56 / 100	274 ms	26220 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <iostream>
#include <map>
using namespace std;

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

	vector<vector<int> > parts;
	vector<int> cyc;

	for(int i = 0; i < n; i ++)
	{
		if(m.count(p[i]) == 0)
		{
			bool two = false;
			bool even = true;
			for(int j = 0; j < n; j ++)
			{
				if(p[i][j] == 1) even = false;
				else if(p[i][j] == 2) two = true;
			}
			if(two && even)
			{
				cyc.push_back(i);
			}
			else
			{
				m[p[i]] = m.size();
				parts.push_back({i});
			}
		}
		else parts[m[p[i]]].push_back(i);
	}



	vector<bool> done(n);
	vector<vector<int> > answer(n, vector<int> (n));
/*
	cerr << "parts:\n";
	for(auto part : parts)
	{
		for(auto el : part) cerr << el << " ";
		cerr << '\n';
	}
	cerr << "cyc:\n";
	for(auto el : cyc) cerr << el << " ";
	cerr << '\n';
*/

	for(int i = 0; i < n; i ++)
	{
		if(done[i]) continue;
		int last = -1;
		int first = -1;

		for(int j = 0; j < parts.size(); j ++)
		{
			if(p[i][parts[j][0]] == 0) continue;


			if(first < 0) first = parts[j][0];


			for(int k = 0; k < parts[j].size(); k ++)
			{
				int cur = parts[j][k];
				done[cur] = true;
				if(k == 0)
				{
					if(last >= 0)
					{
						answer[cur][last] = 1;
						answer[last][cur] = 1;
					}		
				}
				else 
				{
					answer[cur][parts[j][k - 1]] = 1;
					answer[parts[j][k - 1]][cur] = 1;
				}
			}

			last = parts[j][0];
		}

		for(int el : cyc)
		{
			if(p[el][i] > 0)
			{
				done[el] = true;
				if(first < 0) first = el;
				if(last >= 0)
				{
					answer[el][last] = 1;
					answer[last][el] = 1;
				}
				last = el;
			}
		}
		if(last != first) 
		{
			answer[first][last] = 1;
			answer[last][first] = 1;
		}

	}
	

	bool poss = true;
	for(auto part : parts)
	{
		int count = 0;
		for(auto el : p[part[0]]) count += el % 2;
		poss &= (count == part.size());
	}

	if(poss)
	{
		build(answer);
		return 1;
	}
	else return 0;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(int j = 0; j < parts.size(); j ++)
      |                  ~~^~~~~~~~~~~~~~
supertrees.cpp:70:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |    for(int k = 0; k < parts[j].size(); k ++)
      |                   ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:120:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |   poss &= (count == part.size());
      |            ~~~~~~^~~~~~~~~~~~~~

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