Submission #319146

#	Time	Username	Problem	Language	Result	Execution time	Memory
319146		Drew_	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	284 ms	26068 KiB

supertrees

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

#define pb push_back
#define f1 first
#define s2 second

using ii = pair<int, int>;


int const N = 1007;

int ds[N];

int frep(int x)
{
	return ds[x] == x ? x : ds[x] = frep(ds[x]);
}

void join(int x, int y)
{
	x = frep(x); y = frep(y);
	if (x == y)
		return;
	ds[y] = x; //x is parent of y
}

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	for (int i = 0; i < n; ++i)
		ds[i] = i;

	vector<ii> disconnected;
	for (int i = 0; i < n; ++i)
	{
		for (int j = i+1; j < n; ++j)
		{
			if (p[i][j] == 0)
			{
				disconnected.pb({i, j});
				continue;
			}

			if (p[i][j] == 3)
			{
				return 0;
			}

			join(i, j);
		}
	}

	for (ii x : disconnected)
	{
		if (frep(x.f1) == frep(x.s2))
			return 0;
	}

	vector<vector<int>> graph (n);
	vector<vector<int>> _b (n, vector<int> (n, 0));

	for (int i = 0; i < n; ++i)
		graph[frep(i)].pb(i);

	for (int i = 0; i < n; ++i)
		ds[i] = i;

	for (auto g : graph)
	{
		if (g.empty())
			continue;

		for (int i = 0; i < g.size(); ++i)
			for (int j = i+1; j < g.size(); ++j)
		{
			if (p[g[i]][g[j]] == 1)
				join(g[i], g[j]);

			else if (frep(g[i]) == frep(g[j]))
				return 0;
		}

		set<int> st;
		for (int i = 0; i < g.size(); ++i)
		{
			cerr << frep(g[i]) << " - " << g[i] << '\n';
			_b[frep(g[i])][g[i]] = _b[g[i]][frep(g[i])] = 1;
			st.insert(frep(g[i]));
		}

		if (st.size() == 1)
			continue;

		if (st.size() == 2)
			return 0;

		vector<int> node;
		for (int x : st)
			node.pb(x);
		node.pb(*st.begin());

		for (int i = 0; i+1 < node.size(); ++i)
			cerr << node[i] << " -- " << node[i+1] << '\n',
			_b[node[i]][node[i+1]] = _b[node[i+1]][node[i]] = true;
	}

	for (int i = 0; i < n; ++i)
		_b[i][i] = 0;

	build(_b);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:75:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for (int i = 0; i < g.size(); ++i)
      |                   ~~^~~~~~~~~~
supertrees.cpp:76:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |    for (int j = i+1; j < g.size(); ++j)
      |                      ~~^~~~~~~~~~
supertrees.cpp:86:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |   for (int i = 0; i < g.size(); ++i)
      |                   ~~^~~~~~~~~~
supertrees.cpp:104:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for (int i = 0; i+1 < node.size(); ++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