Submission #391167

#	Time	Username	Problem	Language	Result	Execution time	Memory
391167		Karnis_052	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	282 ms	24184 KiB

supertrees

#include<supertrees.h>
#include<bits/stdc++.h>
using namespace std;

int cpar[1005], spar[1005];
set<int>st[1005];

int sfind(int u)
{
	if (spar[u] == u)
		return u;
	return spar[u] = sfind(spar[u]);
}

void sunion(int x, int y)
{
	x = sfind(x);
	y = sfind(y);
	spar[x] = y;
}

int cfind(int u)
{
	if (cpar[u] == u)
		return u;
	return cpar[u] = cfind(cpar[u]);
}

void cunion(int x, int y)
{
	x = cfind(x);
	y = cfind(y);
	cpar[x] = y;
}
int construct(vector<vector<int>>p)
{
	int n = p.size();
	vector<vector<int>>answer(n, vector<int>(n, 0));

	for (int i = 0; i < n; i++)
		cpar[i] = spar[i] = i;
	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (p[i][j] == 0)
				continue;
			if (p[i][j] == 1)
			{
				if (sfind(i) == sfind(j))
					continue;
				sunion(i, j);
				answer[i][j] = answer[j][i] = 1;
			}
			if (p[i][j] >= 2)
				cunion(i, j);
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (p[i][j] == 0)
			{
				if (sfind(i) == sfind(j) or cfind(i) == cfind(j))
					return 0;
			}
			if (p[i][j] == 1)
			{
				if (sfind(i) != sfind(j))
					return 0;
			}
			if (p[i][j] >= 2)
			{
				if (sfind(i) == sfind(j) or cfind(i) != cfind(j))
					return 0;
				st[cfind(i)].insert(p[i][j]);
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		if (cfind(i) != i)
			continue;
		set<int>rem;
		for (int j = 0; j < n; j++)
		{
			if (cfind(j) != i)
				continue;
			rem.insert(sfind(j));
		}
		vector<int>v;
		for (auto it : rem)
			v.push_back(it);
		int k = v.size();
		if (k <= 1)
			continue;
		if (st[i].size() >= 2 or * st[i].begin() == 3)
			return 0;
		if (k <= 2)
			return 0;
		for (int j = 0; j < k; j++)
		{
			int nj = (j + 1) % k;
			answer[v[j]][v[nj]]  = answer[v[nj]][v[j]] = 1;
		}
	}
	build(answer);
	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