Submission #386037

#	Time	Username	Problem	Language	Result	Execution time	Memory
386037		AdOjis485	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	294 ms	28240 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;
	
	for(int i = 0; i < n; i ++)
	{
		if(m.count(p[i]) == 0)
		{
			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';
	}

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

		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;

			numparts ++;

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

		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(comp.size() != compsizei) poss = false;
		if(numparts == 2) 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:46:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   for(int j = 0; j < parts.size(); j ++)
      |                  ~~^~~~~~~~~~~~~~
supertrees.cpp:58:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |    for(int k = 0; k < parts[j].size(); k ++)
      |                   ~~^~~~~~~~~~~~~~~~~
supertrees.cpp:92:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |   if(comp.size() != compsizei) poss = false;
      |      ~~~~~~~~~~~~^~~~~~~~~~~~
supertrees.cpp:100:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   poss &= (count == part.size());
      |            ~~~~~~^~~~~~~~~~~~~~

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