Submission #541846

#	Time	Username	Problem	Language	Result	Execution time	Memory
541846		LucaDantas	Connecting Supertrees (IOI20_supertrees)	C++17	11 / 100	213 ms	23504 KiB

supertrees

#include "supertrees.h"
#include <vector>
using namespace std;

constexpr int maxn = 1010;

vector<vector<int>> ans;
int n;

struct DSU {
	int pai[maxn], peso[maxn], ini[maxn];
	DSU() { for(int i = 0; i < maxn; i++) pai[i] = ini[i] = i, peso[i] = 1; }
	void init(const vector<int>& v) { for(const int& x : v) pai[x] = x, peso[x] = 1, ini[x] = x; }
	int find(int x) { return pai[x] == x ? x : pai[x] = find(pai[x]); }
	void join(int a, int b, bool ans_yes) {
		a = find(a), b = find(b);
		if(a == b) return;
		if(peso[a] < peso[b])
			swap(a, b);
		if(ans_yes)
			ans[ini[a]][b] = ans[b][ini[a]] = 1;
		ini[a] = ini[b];
		pai[b] = a;
		peso[a] += peso[b];
	}
} dsu;

vector<int> comp[maxn], comp2[maxn];

int connected_component(const vector<int>& ativos, const std::vector<std::vector<int>>& p) {
	dsu.init(ativos);
	for(int i : ativos) {
		for(int j : ativos) {
			if(p[i][j] == 1) dsu.join(i, j, 1);
		}
	}

	vector<int> chains;
	for(int i = 0; i < n; i++) {
		if(dsu.find(i) == i) chains.push_back(i);
		comp2[dsu.find(i)].push_back(i);
	}

	for(int i : ativos)
		for(int x : comp2[i])
			for(int y : comp2[i])
				if(p[x][y] != 1) return 0;
	
	if(chains.size() == 1) return 1;
	if(chains.size() == 2) return 0;
	// senao tenho q fazer o ciclo
	int last = chains.back();
	for(int x : chains)
		ans[x][last] = ans[last][x] = 1, last = x; // junto todas as cabecas em um ciclo

	return 1;
}

int construct(std::vector<std::vector<int>> p) {
	n = p.size();
	ans.assign(n, vector<int>(n, 0));

	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(p[i][j] != 0) dsu.join(i, j, 0);
			if(p[i][j] == 3) return 0;
		}
	}

	for(int i = 0; i < n; i++)
		comp[dsu.find(i)].push_back(i);

	for(int i = 0; i < n; i++) {
		for(int x : comp[i])
			for(int y : comp[i])
				if(p[x][y] == 0) return 0;
		if(comp[i].size() && connected_component(comp[i], p) == 0) return 0;
	}

	build(ans);
	return 1;
}

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