Submission #605126

#	Time	Username	Problem	Language	Result	Execution time	Memory
605126		CyberCow	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1 ms	320 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <queue>
#include <unordered_set>
#include <map>
using namespace std;
vector<pair<int, int>> v[1005];
int c[1005], c1[1005];
int cnt = 1;
vector<int> gt;

void Dfs(int g)
{
	gt.push_back(g);
	c[g] = cnt;
	for (auto it : v[g])
	{
		if (c[it.first] == 0)
			Dfs(it.first);
	}
}

void Dfs1(int g)
{
	gt.push_back(g);
	c1[g] = cnt;
	for (auto to : v[g])
	{
		if (c1[to.first] == 0)
			Dfs(to.first);
	}
}

int construct(vector<vector<int>> x) {
	int n = x.size();
	vector<vector<int>> ans(n,vector<int>(n));
	int i, j;
	for ( i = 0; i < n; i++)
	{
		for ( j = 0; j < n; j++)
		{
			if (x[i][j] == 3)
				return 0;
			if (x[i][j] == 2)
			{
				v[i].push_back({j, 2});
				v[j].push_back({ i, 1 });
			}
			if (x[i][j] == 1)
			{
				v[i].push_back({ j, 1 });
				v[j].push_back({ i, 1 });
			}
		}
	}
	for ( i = 0; i < n; i++)
	{
		if (c[i] == 0)
		{
			gt.clear();
			Dfs(i);
			cnt++;
			for ( j = 0; j < gt.size() - 1; j++)
			{
				ans[gt[j]][gt[j + 1]] = 1;
				ans[gt[j + 1]][gt[j]] = 1;
			}
		}
	}
	cnt = 1;
	for ( i = 0; i < n; i++)
	{
		if (c1[i] == 0)
		{
			gt.clear();
			Dfs1(i);
			cnt++;
			if (gt.size() > 1)
				for (j = 0; j < gt.size(); j++)
				{
					ans[gt[j]][gt[(j + 1) % gt.size()]] = 1;
					ans[gt[(j + 1) % gt.size()]][gt[j]] = 1;
				}
			
		}
	}
	for ( i = 0; i < n; i++)
	{
		for ( j = 0; j < n; j++)
		{
			if(i != j)
			if ((x[i][j] == 0 && (c[i] == c[j] || c1[i] == c1[j])) || (x[i][j] == 1 && (c[i] != c[j] || c1[i] == c1[j])) || (x[i][j] == 2 && (c[i] == c[j] || c1[i] != c[j])))
				return 0;
		}
	}
	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:63:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |    for ( j = 0; j < gt.size() - 1; j++)
      |                 ~~^~~~~~~~~~~~~~~
supertrees.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for (j = 0; j < gt.size(); j++)
      |                 ~~^~~~~~~~~~~

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