Submission #1005160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005160		thinknoexit	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	115 ms	24148 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1010;
int p[N];
vector<int> g[N];
int fr(int i) {
	return p[i] == i ? i : p[i] = fr(p[i]);
}
int construct(vector<vector<int>> B) {
	int n = B.size();
	for (int i = 0;i < n;i++) p[i] = i;
	vector<vector<int>> ans(n, vector<int>(n, 0));
	for (int i = 0;i < n;i++) {
		for (int j = i + 1;j < n;j++) {
			if (B[i][j]) {
				p[fr(i)] = fr(j);
			}
		}
	}
	for (int i = 0;i < n;i++) {
		g[fr(i)].push_back(i);
	}
	for (int G = 0;G < n;G++) {
		if (g[G].empty() || (int)g[G].size() == 1) continue;
		auto& v = g[G];
		int m = v.size();
		int cnt = 0;
		for (int i = 0;i < m;i++) {
			for (int j = i + 1;j < m;j++) {
				if (B[v[i]][v[j]] == 0) return 0;
				cnt += (B[v[i]][v[j]] == 1);
			}
		}
		if (cnt == m * (m - 1) / 2) {
			for (int i = 1;i < m;i++) {
				ans[v[0]][v[i]] = ans[v[i]][v[0]] = 1;
			}
		}
		else {
			if (m == 2) return 0;
			for (int i = 0;i < m;i++) {
				ans[v[i]][v[(i + 1) % m]] = ans[v[(i + 1) % m]][v[i]] = 1;
			}
		}
	}
	build(ans);
	return 1;
}

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