Submission #386009

#	Time	Username	Problem	Language	Result	Execution time	Memory
386009		AdOjis485	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	324 ms	28012 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> cycp;
	vector<int> cyc;

	for(int i = 0; i < n; i ++)
	{
		if(m.count(p[i]) == 0)
		{
			if(cycp.size() == n && p[i] == cycp) cyc.push_back(i);
			else 
			{
				if(cycp.size() == 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)
					{
						cycp = p[i];
						cyc.push_back(i);
					}
					else
					{
						m[p[i]] = m.size();
						parts.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:21:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   21 |    if(cycp.size() == n && p[i] == cycp) cyc.push_back(i);
      |       ~~~~~~~~~~~~^~~~
supertrees.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for(int j = 0; j < parts.size(); j ++)
      |                  ~~^~~~~~~~~~~~~~
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 k = 0; k < parts[j].size(); k ++)
      |                   ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:134:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |   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