Submission #1143755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143755		choochoo	Connecting Supertrees (IOI20_supertrees)	C++20	96 / 100	123 ms	26120 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ve vector
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<ll,ll>

int par1[1001], par2[1001], check[1001], check2[1001];
ve<int> nodes[1001];
ve<pii> nono;

int root(int u, int* par) {
	if (u == par[u]) return u;
	return par[u] = root(par[u], par);
}

void join(int u, int v, int* par) {
	u = root(u, par); v = root(v, par);
	if (u != v) par[u] = v;
}

int construct(ve<ve<int>> p) {
	int n = p.size();
	ve<ve<int>> answer;
	for (int i = 0; i < n; i++) {
		ve<int> row;
		row.resize(n);
		answer.push_back(row);
	}

	for (int i=0; i<n; i++) {
		par1[i] = i;
		par2[i] = i;
	}
	for (int i=0; i<n; i++) {
		for (int j=i+1; j<n; j++) {
			if (p[i][j] == 0) {
				nono.pb({i,j});
			}
			else if (p[i][j] == 1) {
				if (root(i, par1) != root(j, par1)) {
					join(i, j, par1);
					answer[i][j] = 1;
					answer[j][i] = 1;
				}
			}
			else if (p[i][j] == 2) {
				join(i, j, par2);
			}
		}
	}
	for (auto i:nono) {
		if (root(i.fi, par1) == root(i.se, par1) || root(i.fi, par2) == root(i.se, par2)) {
			return 0;
		}
	}
	for (int i=0; i<n; i++) {
		if (!check[root(i, par1)]) {
			check[root(i, par1)] = 1;
			nodes[root(i, par2)].pb(i);
		}
	}
	for (int i=0; i<n; i++) {
		int u = root(i, par2);
		if (!check2[u] && nodes[u].size() > 2) {
			check2[u] = 1;
			for (int j=0; j<nodes[u].size()-1; j++) {
				answer[nodes[u][j]][nodes[u][j+1]] = 1;
				answer[nodes[u][j+1]][nodes[u][j]] = 1;
			}
			answer[nodes[u][0]][nodes[u][nodes[u].size()-1]] = 1;
			answer[nodes[u][nodes[u].size()-1]][nodes[u][0]] = 1;
		}
		else if (nodes[u].size() == 2) {
			return 0;
		}
	}

	build(answer);
	return 1;
}

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