Submission #792048

#	Time	Username	Problem	Language	Result	Execution time	Memory
792048		mousebeaver	Connecting Supertrees (IOI20_supertrees)	C++14	40 / 100	181 ms	24004 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

int construct(vector<vector<int>> p) 
{
	bool sub1 = true;
	bool sub2 = true;
	int n = p.size();

	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(p[i][j] != 1)
			{
				sub1 = false;
			}
			if(p[i][j] > 1)
			{
				sub2 = false;
			}
		}
	}
	
	if(sub1)
	{
		vector<vector<int>> adjmatrix(n, vector<int> (n, 0));
		for(int i = 0; i < n-1; i++)
		{
			adjmatrix[i][i+1] = 1;
			adjmatrix[i+1][i] = 1;
		}
		build(adjmatrix);
		return 1;
	}
	if(sub2)
	{
		vector<vector<int>> adjmatrix(n, vector<int> (n, 0));
		vector<bool> used(n, false);
		for(int i = 0; i < n; i++)
		{
			if(!used[i])
			{
				vector<int> nodes(0);
				for(int j = 0; j < n; j++)
				{
					if(p[i][j] == 1)
					{
						nodes.push_back(j);
						used[j] = true;
					}
				}

				for(int i : nodes)
				{
					if(count(p[i].begin(), p[i].end(), 1) != (int) nodes.size())
					{
						return 0;
					}
					for(int j : nodes)
					{
						if(p[i][j] != 1)
						{
							return 0;
						}
					}
				}

				for(int i = 0; i < (int) nodes.size()-1; i++)
				{
					adjmatrix[nodes[i]][nodes[i+1]] = 1;
					adjmatrix[nodes[i+1]][nodes[i]] = 1;
				}
			}
		}
		build(adjmatrix);
		return 1;
	}
	
	//sub3:
	vector<vector<int>> adjmatrix(n, vector<int> (n, 0));
	vector<bool> used(n, false);
	for(int i = 0; i < n; i++)
	{
		if(!used[i])
		{
			vector<int> nodes(0);
			for(int j = 0; j < n; j++)
			{
				if(p[i][j] > 0)
				{
					nodes.push_back(j);
					used[j] = true;
				}
			}

			if(nodes.size() == 2)
			{
				return 0;
			}
			for(int i : nodes)
			{
				if(count(p[i].begin(), p[i].end(), 0) != n-nodes.size())
				{
					return 0;
				}
				for(int j : nodes)
				{
					if(p[i][j] == 0)
					{
						return 0;
					}
				}
			}

			for(int i = 0; i < (int) nodes.size()-1; i++)
			{
				adjmatrix[nodes[i]][nodes[i+1]] = 1;
				adjmatrix[nodes[i+1]][nodes[i]] = 1;
			}
			if(nodes.size() > 1)
			{
				adjmatrix[nodes[0]][nodes[nodes.size()-1]] = 1;
				adjmatrix[nodes[nodes.size()-1]][nodes[0]] = 1;
			}
		}
	}
	build(adjmatrix);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:104:43: warning: comparison of integer expressions of different signedness: 'std::__iterator_traits<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, void>::difference_type' {aka 'long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     if(count(p[i].begin(), p[i].end(), 0) != n-nodes.size())
      |        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

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