Submission #463787

#	Time	Username	Problem	Language	Result	Execution time	Memory
463787		armand	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	259 ms	27992 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include <queue>

int pp[1001][1001];
int n;
std::vector<std::vector<int>> answer;

bool all1()
{
	int i, j;
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			if (pp[i][j] != 1)
				return false;
	return true;
}

bool all01()
{
	int i, j;
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			if (pp[i][j] > 1)
				return false;
	return true;
}

bool all02()
{
	int i, j;
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++) {
			if (i == j)
				continue;
			if (pp[i][j] != 0 && pp[i][j] != 2)
				return false;
		}
	return true;
}

void solve1()
{
	int i;
	for (i = 0; i < n - 1; i++) {
		answer[i][i + 1] = 1;
		answer[i + 1][i] = 1;
	}
}

int color[1001];
int nodes[1001];
int nn;
bool flag2, flag3;
int nc;
void dfs(int u, int prnt)
{
	int j;
	for(j=0; j<n; j++)
		if (pp[u][j] && !color[j]) {
			nodes[nn++] = j;
			color[j] = nc;
			dfs(j, u);
		}
}

void solve2()
{
	int i, j;
	for (i = 0; i < n; i++) {
		if (!color[i]) {
			nn = 0;
			nc++;
			color[i] = nc;
			nodes[nn++] = i;
			dfs(i, -1);
			for (j = 1; j < nn; j++) {
				answer[nodes[j]][nodes[j - 1]] = 1;
				answer[nodes[j - 1]][nodes[j]] = 1;
			}
		}
	}
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++) {
			if (i == j)
				continue;
			if (color[i] == color[j] && !pp[i][j])
				flag2 = false;
		}
}

void solve3()
{
	int i, j;
	for (i = 0; i < n; i++) {
		if (!color[i]) {
			nn = 0;
			nc++;
			color[i] = nc;
			nodes[nn++] = i;
			dfs(i, -1);
			if (nn > 2) {
				for (j = 1; j < nn; j++) {
					answer[nodes[j]][nodes[j - 1]] = 1;
					answer[nodes[j - 1]][nodes[j]] = 1;
				}
				answer[nodes[0]][nodes[nn - 1]] = 1;
				answer[nodes[nn - 1]][nodes[0]] = 1;
			}
			else if (nn == 2)
				flag3 = false;
		}
	}
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++) {
			if (i == j)
				continue;
			if (color[i] == color[j] && !pp[i][j])
				flag3 = false;
		}
}

bool flag4;

void solve4()
{
	int i, j, k;
	for (i = 0; i < n; i++) {
		if (!color[i]) {
			nn = 0;
			nc++;
			color[i] = nc;
			nodes[nn++] = i;
			dfs(i, -1);
			if (nn == 1)
				continue;
			std::vector<int> mark;
			std::vector<int> cicle;
			mark.resize(nn);
			for (j = 0; j < nn; j++)
				mark[j] = 0;
			std::queue<int> q;
			for(j=0; j<nn; j++)
				if (mark[j] == 0) {
					q.push(nodes[j]);
					mark[j] = true;
					std::vector<int> line;
					while (!q.empty())
					{
						int x = q.front();
						q.pop();
						for(k=0; k<nn; k++)
							if (pp[x][nodes[k]] == 1 && !mark[k]) {
								line.push_back(nodes[k]);
								mark[k] = true;
								q.push(nodes[k]);
							}
					}
					if (line.size() > 0) {
						line.push_back(nodes[j]);
						cicle.push_back(nodes[j]);
						for (k = 1; k < line.size(); ++k) {
							answer[line[k]][line[k - 1]] = 1;
							answer[line[k - 1]][line[k]] = 1;
						}
					}
					else
						cicle.push_back(nodes[j]);
				}	
			for (j = 1; j < cicle.size(); j++) {
				answer[cicle[j]][cicle[j - 1]] = 1;
				answer[cicle[j - 1]][cicle[j]] = 1;
			}
			if (cicle.size() > 2) {
				answer[cicle[0]][cicle[cicle.size() - 1]] = 1;
				answer[cicle[cicle.size() - 1]][cicle[0]] = 1;
			}
			else if (cicle.size() == 2)
				flag4 = false;
		}
	}
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++) {
			if (i == j)
				continue;
			if (color[i] == color[j] && !pp[i][j])
				flag4 = false;
		}
}

int construct(std::vector<std::vector<int>> p)
{
	n = p.size();
	int i, j;
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++) {
			pp[i][j] = p[i][j];
			if (p[i][j] == 3)
				return 0;
		}
	for (int i = 0; i < n; i++) {
		std::vector<int> row;
		row.resize(n);
		answer.push_back(row);
	}
	if (all1())
		solve1();
	else if (all01()) {
		flag2 = true;
		solve2();
		if (flag2) {
			build(answer);
			return 1;
		}
		return 0;
	}
	else if (all02()) {
		flag3 = true;
		solve3();
		if (flag3) {
			build(answer);
			return 1;
		}
		return 0;
	}
	else {
		flag4 = true;
		solve4();
		if (flag4) {
			build(answer);
			return 1;
		}
		return 0;
	}
	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'void solve4()':
supertrees.cpp:162:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |       for (k = 1; k < line.size(); ++k) {
      |                   ~~^~~~~~~~~~~~~
supertrees.cpp:170:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |    for (j = 1; j < cicle.size(); j++) {
      |                ~~^~~~~~~~~~~~~~

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