Submission #371354

#	Time	Username	Problem	Language	Result	Execution time	Memory
371354		peijar	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	441 ms	23608 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;
	}
};

// On fait le dfs tree en partant d'un sommet quelconque
// Chemin partant d'un sommet : 
//
//

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])
				uf.merge(i, j);
	bool oneTwo(false);
	for (int i(0); i < nbSommets; ++i)
		for (int j(0); j < nbSommets; ++j)
			oneTwo |= p[i][j] == 2;
	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] == 0)
				return 0;
	if (!oneTwo)
	{
		for (int i(0); i < nbSommets; ++i)
			if (uf.find(i) != i)
				sol[uf.find(i)][i] = sol[i][uf.find(i)] = 1;
	}
	else
	{
		auto comps = uf.getComps();
		for (auto v : comps)
			if (SZ(v) > 1)
				for (int i(0); i < SZ(v); ++i)
					p[v[i]][v[(i+1)%SZ(v)]] = p[v[(i+1)%SZ(v)]][v[i]] = 1;
	}
	build(sol);
	return 1;
}

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