Submission #771885

#	Time	Username	Problem	Language	Result	Execution time	Memory
771885		Blagoj	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	161 ms	28176 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"

using namespace std;

int leader[1005], ranking[1005];

int Find(int n) {
	if (leader[n] != n) leader[n] = Find(leader[n]);
	return leader[n];
}

void Union(int x, int y) {
	x = Find(x), y = Find(y);
	if (ranking[x] > ranking[y]) swap(x, y);
	ranking[y] += ranking[x];
	leader[x] = y;
}

vector<int> g[1005];
bool visited[1005];
vector<int> components;

void dfs(int n) {
	visited[n] = 1;
	components.push_back(n);
	for (auto x : g[n]) {
		if (visited[x]) continue;
		dfs(x);
	}
}

int construct(vector<vector<int>> p) {
	int n = p.size();
	for (int i = 0; i <= n; i++) {
		leader[i] = i;
		ranking[i] = 1;
	}
	vector<vector<int>> answer(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (p[i][j] == 3) return 0;
			if (p[i][j] == 1) Union(i, j);
		}
	}
	for (int i = 0; i < n; i++) if (Find(i) != i) answer[Find(i)][i] = answer[i][Find(i)] = 1;
	for (int i = 0; i < n; i++) { 
		for (int j = i + 1; j < n; j++) {
			if (p[i][j] == 0 && Find(i) == Find(j)) return 0;
			if (p[i][j] == 2 && Find(i) == i && Find(j) == j) {
				g[i].push_back(j);
				g[j].push_back(i);
			}
		}
	}
	for (int i = 0; i < n; i++) {
		if (Find(i) != i || visited[i]) continue;
		dfs(i);
		if (components.size() == 2) return 0;
		for (auto x : components) {
			for (auto y : components) if (x != y && p[x][y] != 2) return 0;
		}
		for (int j = 0; j < components.size() - 1; j++) {
			answer[components[j]][components[j + 1]] = answer[components[j + 1]][components[j]] = 1;
		}
		if (components.size() != 1) answer[components[0]][components[components.size() - 1]] = answer[components.size() - 1][components[0]] = 1;
		components.clear();
	}
	build(answer);
	return 1;
}

Compilation message (stderr)

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

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