Submission #524082

#	Time	Username	Problem	Language	Result	Execution time	Memory
524082		prvocislo	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	206 ms	24056 KiB

supertrees

#include "supertrees.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <iomanip>
#include <functional>
#include <bitset>
typedef long long ll;
typedef long double ld;
using namespace std;

//void build(vector<vector<int>> b);
vector<int>f;
vector<vector<int> > b;
void dfs(int vr, vector<int>&v, vector<vector<int>> &p, int edge = -1)
{
	v.push_back(vr);
	f[vr] = 1;
	for (int i = 0; i < p.size(); i++)
	{
		if (i != vr && ((edge == -1 && p[vr][i]) || p[vr][i] == edge) && f[i] == 0)
		{
			dfs(i, v, p, edge);
		}
	}
}
bool create(vector<int>& v, bool cycle = false)
{
	// vytvori strom/cyklus
	if (cycle && v.size() <= 2)
	{
		return false;
	}
	for (int i = 0; i < v.size() - 1; i++)
	{
		b[v[i]][v[i + 1]] = b[v[i + 1]][v[i]] = 1;
	}
	if (cycle)
	{
		b[v[0]][v.back()] = b[v.back()][v[0]] = 1;
	}
	return true;
}
int construct(vector<vector<int>> p)
{
	int n = p.size();
	b.resize(n, vector<int>(n, 0));
	f.resize(n);
	for (int i = 0; i < n; i++)
	{
		if (count(p[i].begin(), p[i].end(), 3)) return 0;
		if (!f[i])
		{
			vector<int>v;
			dfs(i, v, p);
			if (v.size() == 1)
			{
				continue;
			}
			int cc = 0;
			for (int j : v)
			{
				for (int k : v)
				{
					if (!p[j][k])
					{
						return 0;
					}
					if (p[j][k] == 2)
					{
						cc++;
					}
				}
			}
			if (!cc)
			{
				create(v);
				continue;
			}
			for (int j : v)
			{
				f[j] = 0;
			}
			// lubovolny prvok z kazdeho stromu moze byt v cykle!
			// cize spojime tie stromy a spojime lubovolne ich korene
			vector<int> roots;
			for (int j : v)
			{
				if (!f[j])
				{
					roots.push_back(j);
					vector<int>v2;
					dfs(j, v2, p, 1);
					for (int k : v2)
					{
						for (int l : v2)
						{
							if (p[k][l] == 2)
							{
								return 0;
							}
						}
					}
					create(v2);
				}
			}
			if (!create(roots, true))
			{
				return 0;
			}
		}
	}
	build(b);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'void dfs(int, std::vector<int>&, std::vector<std::vector<int> >&, int)':
supertrees.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for (int i = 0; i < p.size(); i++)
      |                  ~~^~~~~~~~~~
supertrees.cpp: In function 'bool create(std::vector<int>&, bool)':
supertrees.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for (int i = 0; i < v.size() - 1; i++)
      |                  ~~^~~~~~~~~~~~~~

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