Submission #1143752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143752		choochoo	Connecting Supertrees (IOI20_supertrees)	C++20	0 / 100	1 ms	328 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];

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++) {
		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] == 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 (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;
		}
	}

	build(answer);
	return 1;
}

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