Submission #391165

#	Time	Username	Problem	Language	Result	Execution time	Memory
391165		Karnis_052	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	3 ms	588 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;
	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;
	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;
}

Compilation message (stderr)

supertrees.cpp: In function 'int sfind(int)':
supertrees.cpp:12:10: warning: control reaches end of non-void function [-Wreturn-type]
   12 |  spar[u] = sfind(spar[u]);
      |  ~~~~~~~~^~~~~~~~~~~~~~~~
supertrees.cpp: In function 'int cfind(int)':
supertrees.cpp:26:10: warning: control reaches end of non-void function [-Wreturn-type]
   26 |  cpar[u] = cfind(cpar[u]);
      |  ~~~~~~~~^~~~~~~~~~~~~~~~

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