Submission #1196148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196148		noabenysrael	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	117 ms	22320 KiB

supertrees

#include <vector>
#include <iostream>
#include <set>
#include "supertrees.h"

using namespace std;
using ll = int;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using pll = pair<int, int>;
using vb = vector<bool>;
using vpll = vector <pll>;


vvll partition(vll &nums, vvll &p, ll u_bound, ll l_bound) {
	vvll part;
	ll n = nums.size();
	vb vis(n, 0);
	for (ll i = 0; i < n; i++) {
		if (vis[i]) continue;
		part.push_back({ nums[i] });
		vis[i] = 1;
		for (ll j = i + 1; j < n; j++) {
			if (p[nums[i]][nums[j]] >= l_bound && p[nums[i]][nums[j]] <= u_bound) {
				vis[j] = true;
				part.back().push_back(nums[j]);
			}
		}
	}
	return part;
}

int construct(std::vector<std::vector<int>> p) {
	ll n = p.size();
	for (ll i = 0; i < n; i++) {
		if (p[i][i] != 1) return 0;
	}
	for (ll i = 0; i < n; i++) {
		for (ll j = i + 1; j < n; j++) {
			if (p[i][j] != p[j][i]) return 0;
			if (p[i][j] == 3) return 0;
		}
	}
	vll nums(n);
	for (ll i = 0; i < n; i++) nums[i] = i;
	vvll part1 = partition(nums, p, 2, 1);
	vvvll part;
	for (vll& v : part1) {
		part.push_back(partition(v, p, 1, 1));
	}
	vpll locs(n);
	for (ll comp = 0; comp < part.size(); comp++) {
		for (ll tree = 0; tree < part[comp].size(); tree++) {
			for (ll v : part[comp][tree]) {
				locs[v] = { comp, tree };
			}
		}
	}
	for (ll i = 0; i < n; i++) {
		for (ll j = i + 1; j < n; j++) {
			if (locs[i].first != locs[j].first) {
				if (p[i][j] != 0) return 0;
			}
			else if (locs[i].second == locs[j].second) {
				if (p[i][j] != 1) return 0;
			}
			else if (p[i][j] != 2) return 0;
		}
	}
	vvll b(n, vll(n, 0));
	for (vvll& comp : part) {
		if (comp.size() == 2) return 0;	
		for (vll& tree : comp) {
			for (ll i = 1; i < tree.size(); i++) {
				b[tree[i]][tree[0]] = 1;
				b[tree[0]][tree[i]] = 1;
			}
		}
		if (comp.size() > 1) {
			for (ll i = 0; i < comp.size(); i++) {
				b[comp[i][0]][comp[(i + 1) % comp.size()][0]] = 1;
				b[comp[(i + 1) % comp.size()][0]][comp[i][0]] = 1;
			}
		}
	}
	build(b);
	return 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