Submission #1077977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077977		Tsovak	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	170 ms	29096 KiB

supertrees

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

const int N = 1005;
int c[N][N];
bool ans[N][N];
int n;

int p[N];

int gp(int u)
{
	if (u == p[u]) return u;
	return p[u] = gp(p[u]);
}

void us(int u, int v)
{
	u = gp(u); v = gp(v);
	p[v] = u;

	return;
}

vector<int> vv[N];

bool allare(vector<int>& v, int h)
{
	int i, j;

	for (i = 0; i < v.size() - 1; i++) {
		for (j = i + 1; j < v.size(); j++) {
			if (c[v[i]][v[j]] != h) return false;
		}
	}

	return true;
}

int construct(vector<vector<int>> p0)
{
	int i, j, k;
	int u, v;

	n = p0.size();
	for (i = 0; i < n; i++) for (j = 0; j < n; j++) c[i + 1][j + 1] = p0[i][j];


	for (i = 1; i <= n; i++) p[i] = i;

	for (i = 1; i < n; i++) {
		for (j = i + 1; j <= n; j++) {
			if (c[i][j] == 3) return 0;

			if (c[i][j]) us(i, j);
		}
	}

	for (i = 1; i < n; i++) {
		for (j = i + 1; j <= n; j++) {
			if (c[i][j]) continue;

			if (gp(i) == gp(j)) return 0;
		}
	}

	for (i = 1; i <= n; i++) vv[gp(i)].push_back(i);

	for (i = 1; i <= n; i++) {
		if (vv[i].size() <= 1) continue;

		if (allare(vv[i], 1)) {
			for (j = 0; j < vv[i].size() - 1; j++) ans[vv[i][j]][vv[i][j + 1]] = ans[vv[i][j + 1]][vv[i][j]] = 1;

			continue;
		}

		if (allare(vv[i], 2)) {
			if (vv[i].size() == 2) return 0;

			for (j = 0; j < vv[i].size() - 1; j++) ans[vv[i][j]][vv[i][j + 1]] = ans[vv[i][j + 1]][vv[i][j]] = 1;
			ans[vv[i].back()][vv[i].front()] = ans[vv[i].front()][vv[i].back()] = 1;

			continue;
		}


		for (j = 1; j <= n; j++) p[j] = j;

		for (j = 0; j < vv[i].size() - 1; j++) {
			for (k = j + 1; k < vv[i].size(); k++) {
				u = vv[i][j]; v = vv[i][k];

				if (c[u][v] == 1) us(u, v);
			}
		}

		for (j = 0; j < vv[i].size() - 1; j++) {
			for (k = j + 1; k < vv[i].size(); k++) {
				u = vv[i][j]; v = vv[i][k];

				if (c[u][v] == 2 && gp(u) == gp(v)) return 0;
			}
		}


		set<int> st;

		for (j = 0; j < vv[i].size(); j++) {
			u = vv[i][j];

			st.insert(gp(u));

			if (u != gp(u)) ans[u][gp(u)] = ans[gp(u)][u] = 1;
		}

		vector<int> ve;
		for (auto x : st) ve.push_back(x);

		if (ve.size() <= 2) return 0;

		for (j = 0; j < ve.size() - 1; j++) ans[ve[j]][ve[j + 1]] = ans[ve[j + 1]][ve[j]] = 1;
		ans[ve.back()][ve.front()] = ans[ve.front()][ve.back()] = 1;
	}

	vector<vector<int>> res(n, vector<int>(n));

	for (i = 0; i < n; i++) for (j = 0; j < n; j++) res[i][j] = ans[i + 1][j + 1];

	build(res);

	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'bool allare(std::vector<int>&, int)':
supertrees.cpp:32:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for (i = 0; i < v.size() - 1; i++) {
      |              ~~^~~~~~~~~~~~~~
supertrees.cpp:33:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for (j = i + 1; j < v.size(); j++) {
      |                   ~~^~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:74:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |    for (j = 0; j < vv[i].size() - 1; j++) ans[vv[i][j]][vv[i][j + 1]] = ans[vv[i][j + 1]][vv[i][j]] = 1;
      |                ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |    for (j = 0; j < vv[i].size() - 1; j++) ans[vv[i][j]][vv[i][j + 1]] = ans[vv[i][j + 1]][vv[i][j]] = 1;
      |                ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:91:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |   for (j = 0; j < vv[i].size() - 1; j++) {
      |               ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:92:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |    for (k = j + 1; k < vv[i].size(); k++) {
      |                    ~~^~~~~~~~~~~~~~
supertrees.cpp:99:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for (j = 0; j < vv[i].size() - 1; j++) {
      |               ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:100:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |    for (k = j + 1; k < vv[i].size(); k++) {
      |                    ~~^~~~~~~~~~~~~~
supertrees.cpp:110:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   for (j = 0; j < vv[i].size(); j++) {
      |               ~~^~~~~~~~~~~~~~
supertrees.cpp:123:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |   for (j = 0; j < ve.size() - 1; j++) ans[ve[j]][ve[j + 1]] = ans[ve[j + 1]][ve[j]] = 1;
      |               ~~^~~~~~~~~~~~~~~

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