Submission #1005216

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005216		thinknoexit	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	144 ms	22284 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1010;
int p[N], p2[N];
int fr(int i) {
	return p[i] == i ? i : p[i] = fr(p[i]);
}
int fr2(int i) {
	return p2[i] == i ? i : p2[i] = fr2(p2[i]);
}
int construct(vector<vector<int>> B) {
	int n = B.size();
	vector<vector<int>> ans(n, vector<int>(n, 0));
	// Calculate for p[i][j] = 1
	iota(p, p + n, 0);
	for (int i = 0;i < n;i++) {
		for (int j = i + 1;j < n;j++) {
			if (B[i][j] == 1) {
				p[fr(i)] = fr(j);
			}
			if (B[i][j] == 3) return 0;
		}
	}
	vector<vector<int>> g(n);
	for (int i = 0;i < n;i++) {
		g[fr(i)].push_back(i);
	}
	vector<int> node;
	for (int G = 0;G < n;G++) {
		if (g[G].empty()) continue;
		node.push_back(G);
		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]] != 1) return 0;
			}
		}
		for (int i = 1;i < m;i++) {
			ans[v[0]][v[i]] = ans[v[i]][v[0]] = 1;
		}
	}
	iota(p2, p2 + n, 0);
	int k = node.size();
	for (int i = 0;i < k;i++) {
		for (int j = i + 1;j < k;j++) {
			if (B[node[i]][node[j]] == 2) {
				p2[fr2(node[i])] = fr2(node[j]);
			}
		}
	}
	vector<vector<int>> g2(n);
	for (int i = 0;i < k;i++) {
		g2[fr2(node[i])].push_back(node[i]);
	}
	for (int G = 0;G < n;G++) {
		if (g2[G].empty() || (int)g2[G].size() == 1) continue;
		if ((int)g2[G].size() == 2) return 0;
		auto& v = g2[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]] != 2) return 0;
			}
		}
		for (int i = 0;i < m;i++) {
			ans[v[(i + 1) % m]][v[i]] = ans[v[i]][v[(i + 1) % m]] = 1;
		}
	}
	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:36:7: warning: unused variable 'cnt' [-Wunused-variable]
   36 |   int cnt = 0;
      |       ^~~
supertrees.cpp:64:7: warning: unused variable 'cnt' [-Wunused-variable]
   64 |   int cnt = 0;
      |       ^~~

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