Submission #795425

#	Time	Username	Problem	Language	Result	Execution time	Memory
795425		adrilen	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	233 ms	26180 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 };
bool done[maxn] = { 0 };

vector <int> adj[2][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[i]) goto impossible;
		}

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

		set <int> seen;
		for (int y = 0; y < i; y++)
		{
			if (seen.count(groups[y])) continue;

			if (p[i][y] == 2) {
				adj[0][g].push_back(groups[y]);
				adj[0][groups[y]].push_back(g);
			}
			if (p[i][y] == 3) {
				adj[1][g].push_back(groups[y]);
				adj[1][groups[y]].push_back(g);
			}
			seen.insert(groups[y]);
		}
	}


	// 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;

		if (!adj[0][i].empty() && !adj[1][i].empty()) goto impossible;

		int t;
		if (!adj[0][i].empty()) t = 0;
		else t = 1;
		
		
		vector<int> gs = adj[t][i];
		gs.insert(gs.begin(), i);

		if (gs.size() == 1) continue;
		if (gs.size() == 2) goto impossible;

		for (int x : gs)
		{
			if (!adj[t ^ 1][x].empty()) goto impossible;

			vector<int> test = adj[t][x];
			test.insert(lower_bound(test.begin(), test.end(), x), x);

			if (test != gs) goto impossible;

			assert(!done[x]);
			done[x] = true;
		}

		// Make a cycle
		for (int y = 0; y < (int)gs.size() - 1; y++) {
			output[gnode[gs[y]]][gnode[gs[y + 1]]] = output[gnode[gs[y + 1]]][gnode[gs[y]]] = 1;
		}
		output[gnode[gs[0]]][gnode[gs[gs.size() - 1]]] = output[gnode[gs[gs.size() - 1]]][gnode[gs[0]]] = 1;


		if (t == 0)
		{
			if (gs.size() < 3) goto impossible;
		}
		else
		{
			goto impossible;
		}
	}


	
	// Build
	build(output);
	return 1;


impossible:

	return 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