Submission #603716

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

supertrees

#include "supertrees.h"
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
vector<pair<int, int>> g[1005];
vector<int> a, gt;
int qaq = 1;

void Dfs1(int ga)
{
	gt.push_back(ga);
	a[ga] = 1;
	for (pair<int, int> to : g[ga])
	{
		if (a[to.first] == 0 && to.second == 1)
		{
			Dfs1(to.first);
		}
	}
}

void Dfs2(int ga)
{
	a[ga] = qaq;
	for (auto to : g[ga])
	{
		if (to.second == 1 && a[to.first] == qaq)
			return;
	}
	gt.push_back(ga);
	for (auto to : g[ga])
	{
		if (a[to.first] == 0 && to.second == 2)
			Dfs2(to.first);
	}
}

int construct(vector<vector<int>> p) {
	int n = p.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 (i != j && p[i][j] != 0)
			{
				g[i].push_back({ j, p[i][j] });
			}
		}
	}
	for ( i = 0; i < n; i++)
	{
		a.push_back(0);
	}
	for ( i = 0; i < n; i++)
	{
		if (a[i] == 0 && g[i].size())
		{
			Dfs1(i);
			for ( j = 0; j < gt.size() - 1; j++)
			{
				ans[gt[j]][gt[j + 1]] = 1;
				ans[gt[j + 1]][gt[j]] = 1;
			}
			gt.clear();
		}
	}
	for ( i = 0; i < n; i++)
	{
		a[i] = 0;
	}
	for ( i = 0; i < n; i++)
	{
		if (a[i] == 0 && g[i].size())
		{
			Dfs2(i);
			if (gt.size())
				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;
				}
			gt.clear();
			qaq++;
		}
	}
	build(ans);
	return 1;
}

Compilation message (stderr)

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