Submission #781055

#	Time	Username	Problem	Language	Result	Execution time	Memory
781055		zsombor	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	175 ms	27980 KiB

supertrees

#include "supertrees.h"
#include <vector>
using namespace std;

int n;
bool impossible = false;
vector <vector <int>> P;
vector <vector <int>> E;

void solve_comp(vector <int>& c) {
	int cnt = 0;
	vector <int> tree(n);
	vector <int> root;
	for (int& i : c) {
		tree[i] = cnt;
		for (int& j : c) { if (i == j) break; if (P[i][j] == 1) tree[i] = tree[j]; }
		for (int& j : c) {
			if (i == j) break;
			if (P[i][j] == 1 && tree[i] != tree[j]) impossible = true;
			if (P[i][j] == 2 && tree[i] == tree[j]) impossible = true;
		}
		if (tree[i] == cnt) { root.push_back(i); cnt++; }
	}
	for (int& i : c) if (i != root[tree[i]]) E[i][root[tree[i]]] = E[root[tree[i]]][i] = 1;
	if (cnt == 1) return;
	if (cnt == 2) { impossible = true; return; }
	for (int i = 1; i < root.size(); i++) E[root[i]][root[i - 1]] = E[root[i - 1]][root[i]] = 1;
	E[root[0]][root.back()] = E[root.back()][root[0]] = 1;
}

int construct(vector <vector <int>> p) {
	n = p.size();
	P = p;
	E.resize(n);
	for (int i = 0; i < n; i++) E[i].assign(n, 0);
	
	int cnt = 0;
	vector <int> comp(n);
	vector <vector <int>> C(n + 1);
	for (int i = 0; i < n; i++) {
		comp[i] = cnt;
		for (int j = 0; j < i; j++) if (P[i][j]) comp[i] = comp[j];
		for (int j = 0; j < i; j++) {
			if (P[i][j] == 3) return 0;
			if (P[i][j] && comp[i] != comp[j]) return 0;
			if (!P[i][j] && comp[i] == comp[j]) return 0;
		}
		C[comp[i]].push_back(i);
		if (comp[i] == cnt) cnt++;
	}

	for (int i = 0; i < cnt; i++) solve_comp(C[i]);
	if (impossible) return 0;
	build(E);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'void solve_comp(std::vector<int>&)':
supertrees.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for (int i = 1; i < root.size(); i++) E[root[i]][root[i - 1]] = E[root[i - 1]][root[i]] = 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