Submission #386015

#	Time	Username	Problem	Language	Result	Execution time	Memory
386015		AdOjis485	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	295 ms	26296 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';
*/

	bool poss = true;
	for(int i = 0; i < n; i ++)
	{
		vector<int> comp;
		if(done[i]) continue;
		int last = -1;
		int first = -1;
		int compsizecount = 0;

		int compsizei = 0;
		for(int j = 0; j < n; j ++) compsizei += (p[i][j] > 0);

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


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

			int compsizecur = 0;
			for(int el : p[parts[j][0]]) compsizecur += (el > 0);
			if(compsizecur != compsizei) poss = false;

			for(int k = 0; k < parts[j].size(); k ++)
			{
				int cur = parts[j][k];
				done[cur] = true;
				comp.push_back(cur);
				compsizecount ++;
				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;
				compsizecount ++;
				comp.push_back(el);

				int compsizecur = 0;
				for(int el2 : p[el]) compsizecur += (el2 > 0);
				if(compsizecur != compsizei) poss = false;

				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;
		}

		for(int a : comp)
		{
			for(int b : comp) if(p[a][b] == 0) poss = false;
		}

		if(compsizecount != compsizei) poss = false;
	}
	
	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:68:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for(int j = 0; j < parts.size(); j ++)
      |                  ~~^~~~~~~~~~~~~~
supertrees.cpp:79:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |    for(int k = 0; k < parts[j].size(); k ++)
      |                   ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:142:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |   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