Submission #1204712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204712		franuch	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	125 ms	26156 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back

ll V;
vc<vc<ll>> a;
vc<vc<ll>> cms;
vc<ll> cid;
vc<vc<ll>> ans;

bool divide() {
	cms.pub({0});
	cid.resize(V);
	cid[0] = 0;
	for (ll i = 1; i < V; i++) {
		ll id = -1;
		ll cnt = 0;
		for (ll j = 0; j < i; j++) {
			if (a[i][j] == 0)
				continue;
			if (id != -1 and cid[j] != id)
				return false;
			id = cid[j];
			cnt++;
		}
		if (id == -1) {
			cid[i] = sz(cms);
			cms.pub({i});
		} else {
			if (cnt < sz(cms[id]))
				return false;
			cid[i] = id;
			cms[id].pub(i);
		}	
	}
	return true;
}

bool make(vc<ll> &com) {
	vc<vc<ll>> dms;
	vc<ll> did(V, 0);
	dms.pub({com[0]});
	did[com[0]] = 0;
	for (ll i = 1; i < sz(com); i++) {
		ll v = com[i];
		ll cnt = 0;
		ll id = -1;
		for (ll j = 0; j < i; j++) {
			ll w = com[j];
			if (a[v][w] == 2)
				continue;
			if (id != -1 and did[w] != id)
				return false;
			id = did[w];
			cnt++;
		}
		if (id == -1) {
			did[v] = sz(dms);
			dms.pub({v});
		} else {
			if (cnt < sz(dms[id]))
				return false;
			did[v] = id;
			dms[id].pub(v);
		}
	}
	for (auto &dom : dms) {
		for (ll i = 0; i + 1 < sz(dom); i++)
			ans[dom[i]][dom[i + 1]] = 1;
	}
	if (sz(dms) == 1)
		return true;
	if (sz(dms) == 2)
		return false;
	for (ll i = 0; i + 1 < sz(dms); i++)
		ans[dms[i][0]][dms[i + 1][0]] = 1;
	ans[dms[sz(dms) - 1][0]][dms[0][0]] = 1;
	return true;
}

void fix() {
	for (ll i = 0; i < V; i++)
		for (ll j = 0; j < V; j++)
			ans[i][j] = ans[j][i] = max(ans[i][j], ans[j][i]);
}

ll construct(vc<vc<ll>> p) {
	a = p;
	V = sz(a);
	for (ll i = 0; i < V; i++)
		for (ll j = 0; j < V; j++)
			if (a[i][j] == 3)
				return 0;
	
	if (not divide())
		return 0;
	
	ans.assign(V, vc<ll>(V, 0));
	for (auto &com : cms)
		if (not make(com))
			return 0;
	
	fix();
	build(ans);
	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