Submission #372466

#	Time	Username	Problem	Language	Result	Execution time	Memory
372466		peijar	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	290 ms	24172 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define SZ(v) ((int)(v).size())
using namespace std;

using ll = long long;

struct UnionFind
{
	vector<int> id;
	
	UnionFind() {}
	UnionFind(int N)
	{
		id.assign(N, -1);
	}

	int find(int u)
	{
		if (id[u] < 0) return u;
		return id[u] = find(id[u]);
	}

	bool merge(int u, int v)
	{
		u = find(u), v = find(v);
		if (u == v) return false;
		if (id[u] > id[v]) swap(u, v);
		id[u] += id[v];
		id[v] = u;
		return true;
	}

	vector<vector<int>> getComps()
	{
		vector<vector<int>> ret;
		vector<vector<int>> comps(SZ(id));
		for (int i(0); i < SZ(id); ++i)
			comps[find(i)].push_back(i);
		for (auto v : comps)
			if (SZ(v))
				ret.push_back(v);
		return ret;
	}
};


int construct(vector<vector<int>> p) 
{
	int nbSommets = SZ(p);
	vector<vector<int>> sol(nbSommets, vector<int>(nbSommets));

	UnionFind uf(nbSommets);
	for (int i(0); i < nbSommets; ++i)
		for (int j(i+1); j < nbSommets; ++j)
			if (p[i][j] == 3)
				return 0;
	for (int i(0); i < nbSommets; ++i)
		for (int j(i+1); j < nbSommets; ++j)
			if (p[i][j] == 1)
				uf.merge(i,j);
	for (int i(0); i < nbSommets; ++i)
		for (int j(i+1); j < nbSommets; ++j)
			if (uf.find(i) == uf.find(j) and p[i][j] != 1)
				return 0;
	for (int i(0); i< nbSommets; ++i)
		if (uf.find(i) != i)
			sol[uf.find(i)][i] = sol[i][uf.find(i)] = 1;
	UnionFind uf2(nbSommets);
	for (int i(0); i < nbSommets; ++i)
		for (int j(i+1); j < nbSommets; ++j)
			if (p[i][j])
				uf2.merge(i, j);
	for (int i(0); i < nbSommets; ++i)
		for (int j(i+1); j < nbSommets; ++j)
			if (uf2.find(i) == uf2.find(j) and uf.find(i) != uf.find(j) and p[i][j] != 2)
				return 0; 
	auto comps = uf2.getComps();
	for (auto v : comps)
	{
		vector<int> roots;
		for (auto u : v)
			if (uf.find(u) == u)
				roots.push_back(u);
		if (SZ(roots) == 1) continue;
		bool aTwo(false);
		for (auto u : v)
			for (auto w : v)
				if (p[u][w] == 2)
					aTwo = true;
		if (aTwo and SZ(roots) <= 2)
			return 0;
		roots.push_back(roots.front());
		for (int i(1); i < SZ(roots); ++i)
			sol[roots[i-1]][roots[i]] = sol[roots[i]][roots[i-1]] = true;
	}
	build(sol);
	return 1;
}

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