Submission #794672

#	Time	Username	Problem	Language	Result	Execution time	Memory
794672		adrilen	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	151 ms	22424 KiB

supertrees

#include "supertrees.h"
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using arr = array<int, 2>;
using arrr = array<int, 3>;

constexpr int maxn = 1e3 + 5;

int next_group = 1;
int groups[maxn] = { 0 }, gnode[maxn] = { 0 }, siz[maxn] = { 0 };
bool done[maxn] = { 0 };

vector <int> adj[maxn];


int construct(std::vector<std::vector<int>> p) {



	int g;
	int n = p.size();

	vector<vector<int>> output(n, vector<int>(n));


	for (int i = 0; i < n; i++)
	{
		if (groups[i]) continue;

		g = next_group++;

		vector<int> clique = { i };

		for (int y = i + 1; y < n; y++)
		{
			if (p[i][y] == 1) clique.emplace_back(y);
		}
		gnode[g] = i;

		for (int y : clique) {
			groups[y] = g;

			if (p[y] != p[gnode[g]]) goto impossible;
		}

		for (int i = 1; i < (int)clique.size(); i++)
		{
			output[clique[i]][clique[i - 1]] = output[clique[i - 1]][clique[i]] = 1;
		}

		siz[g] = clique.size();

		set <int> seen;
		for (int y = 0; y < i; y++)
		{
			if (p[i][y] != 0 && seen.count(groups[y]) == 0) {
				adj[g].push_back(groups[y]);
				seen.insert(groups[y]);
				adj[groups[y]].push_back(g);
			}
		}
	}

	// cerr << "Groups complete\n";

	// Combining groups
	// in each connected component, there must be either 2, 3, or none, but not both

	for (int i = 1; i < next_group; i++)
	{
		if (done[i]) continue;

		vector<int> gs = adj[i];
		gs.push_back(i);

		vector<int> twos, threes, ones;

		if (gs.size() == 1) continue;

		for (int x : gs)
		{
			int one = 0;
			bool two, three;
			two = three = false;

			for (int y : p[x])
			{
				if (y == 1) one ++;
				else if (y == 2) two = true;
				else if (y == 3) three = true;
			}

			if (two && three) goto impossible;
			
			if (one > 1) {ones.emplace_back(x); continue;}
			
			if (two) twos.emplace_back(x);
			else if (three) threes.emplace_back(x);
		}

		// cout << "Counting finished\n";

		// cerr << ones.size() << " " << twos.size() << " " << threes.size() << " \n";

		if (threes.empty())
		{
			// Twos

			if (twos.size() < ones.size()) goto impossible;

			// Connect the ring to the arms
			for (int y = 0; y < (int)ones.size(); y++) output[gnode[ones[y]]][gnode[twos[y]]] = output[gnode[twos[y]]][gnode[ones[y]]] = 1;

			// Connect the ring
			for (int y = 0; y < (int)twos.size() - 1; y++) 
				output[gnode[twos[y]]][gnode[twos[y + 1]]] = output[gnode[twos[y + 1]]][gnode[twos[y]]] = 1;

			output[gnode[twos[0]]][gnode[twos[twos.size() - 1]]] = output[gnode[twos[twos.size() - 1]]][gnode[twos[0]]] = 1;
		}
	}


	
	// Build
	build(output);
	return 1;


	impossible:

	return 0;
}

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