Submission #786617

#	Time	Username	Problem	Language	Result	Execution time	Memory
786617		Pablo_No	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	172 ms	22288 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <iostream>

using namespace std;

vector<int> cc, cc2, rr;
int n;
vector<int> used, used2;

void dfs(int v, const vector<vector<int>>& g)
{
	used[v] = true;
	cc.push_back(v);
	for(int u = 0; u < n; u++) if(g[v][u] && !used[u])
		dfs(u, g);
}

void dfs2(int v, const vector<vector<int>>& g)
{
	used2[v] = true;
	cc2.push_back(v);
	for(int u = 0; u < n; u++) if(g[v][u] == 1 && !used2[u])
		dfs2(u, g);
}

int construct(std::vector<std::vector<int>> p) {
	n = p.size();

	for(int a = 0; a < n; a++)
		for(int b = 0; b < n; b++)
			if(p[a][b] != p[b][a])
				return 0;

	vector<vector<int>> ans(n, vector<int>(n, 0));

	used.assign(n, 0);

	for(int i = 0; i < n; i++) if(!used[i])
	{
		cc.clear();
		dfs(i, p);

		used2.assign(n, 0);

		rr.clear();

		for(int j : cc) if(!used2[j])
		{
			cc2.clear();
			dfs2(j, p);

			/// Check not dif on cc of 1
			for(auto a : cc2)
				for(auto b : cc2) if(a != b)
				{
					if(p[a][b] != 1)
						return 0;
				}

			for(int k = 0; k < cc2.size()-1; k++)
			{
				ans[cc2[k]][cc2[k+1]] = 1;
				ans[cc2[k+1]][cc2[k]] = 1;
			}

			rr.push_back(j);
		}
		if(rr.size() == 1)
			continue;
		int typ = p[rr[0]][rr[1]];

		if(rr.size() <= typ)
			return 0;
		
		if(typ == 3)
			return 0;
		
		
		for(auto a : rr)
		{
			for(auto b : rr) if(a != b)
			{
				if(p[a][b] != typ)
				{
					return 0;
				}
			}
		}

		if(typ == 2)
		{
			for(int j = 0; j < rr.size()-1; j++)
			{
				ans[rr[j]][rr[j+1]] = 1;
				ans[rr[j+1]][rr[j]] = 1;
			}
			ans[rr[0]][rr[rr.size()-1]] = 1;
			ans[rr[rr.size()-1]][rr[0]] = 1;
		}
		if(typ == 3)
		{
			for(int j = 0; j < rr.size()-2; j++)
			{
				ans[rr[j]][rr[j+1]] = 1;
				ans[rr[j+1]][rr[j]] = 1;
			}
			ans[rr[0]][rr[rr.size()-2]] = 1;
			ans[rr[rr.size()-2]][rr[0]] = 1;

			ans[rr[0]][rr[rr.size()-1]] = 1;
			ans[rr[rr.size()-1]][rr[0]] = 1;

			ans[rr[1]][rr[rr.size()-1]] = 1;
			ans[rr[rr.size()-1]][rr[1]] = 1;
		}
	}
	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:61:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |    for(int k = 0; k < cc2.size()-1; k++)
      |                   ~~^~~~~~~~~~~~~~
supertrees.cpp:73:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |   if(rr.size() <= typ)
      |      ~~~~~~~~~~^~~~~~
supertrees.cpp:93:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |    for(int j = 0; j < rr.size()-1; j++)
      |                   ~~^~~~~~~~~~~~~
supertrees.cpp:103:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |    for(int j = 0; j < rr.size()-2; j++)
      |                   ~~^~~~~~~~~~~~~

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