Submission #642210

#	Time	Username	Problem	Language	Result	Execution time	Memory
642210		CyberCow	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	190 ms	28336 KiB

supertrees

#include "supertrees.h"
#include <iostream>
#include <map>
#include <vector>
using namespace std;
vector<int> v1[1005], v2[1005];
int color1[1005], color2[1005], c1 = 1, c2 = 1;
int sk[1005], qan[1005], vr[1005], anc1[1005], anc2[1005];
int ska[1005], vra[1005], ogt[1005], ogtdfs[1005];

void Dfs1(int g)
{
	color1[g] = c1;
	for (auto to: v1[g])
	{
		if (color1[to] == 0)
		{
			Dfs1(to);
		}
	}
}

void Dfs2(int g)
{
	color2[g] = c2;
	ogtdfs[color1[g]] = 1;
	for (auto to : v2[g])
	{
		if (color2[to] == 0 && ogtdfs[color1[to]] == 0)
		{
			Dfs2(to);
		}
	}
}

int construct(vector<vector<int>> x)
{
	int n = x.size(), i, j, st = 1;
	for ( i = 0; i < n; i++)
	{
		for ( j = 0; j < n; j++)
		{
			if (i == j)
				continue;
			if (x[i][j] == 3)
				return 0;
			else if (x[i][j] == 2)
				v2[i].push_back(j);
			else if (x[i][j] == 1)
				v1[i].push_back(j);
		}
	}
	for ( i = 0; i < n; i++)
	{
		if (color1[i] == 0)
		{
			Dfs1(i);
			c1++;
		}
	}
	for ( i = 0; i < n; i++)
	{
		if (color2[i] == 0)
		{
			Dfs2(i);
			c2++;
		}
	}
	for (i = 0; i <= n; i++)
	{
		sk[i] = -1;
		anc1[i] = -1;
		anc2[i] = -1;
	}
	for ( i = 0; i < n; i++)
	{
		if (sk[color2[i]] == -1)
			sk[color2[i]] = i;
		vr[color2[i]] = i;
		qan[color2[i]]++;
	}
	for ( i = 0; i <= n; i++)
	{
		if (qan[color2[i]] == 2)
			return 0;
	}
	for ( i = 0; i < n; i++)
	{
		for ( j = 0; j < n; j++)
		{
			if (i == j)continue;
			if (color1[i] == color1[j] && x[i][j] == 2)
				return 0;
			if ((color1[i] == color1[j] || color2[i] == color2[j]) && x[i][j] == 0)
				return 0;
		}
	}
	vector<vector<int>> ans(n, vector<int>(n, 0));
	for ( i = 0; i < n; i++)
	{
		if (anc1[color1[i]] == -1)
			anc1[color1[i]] = i;
		else
		{
			ans[i][anc1[color1[i]]] = 1;
			ans[anc1[color1[i]]][i] = 1;
			anc1[color1[i]] = i;
		}
		if (anc2[color2[i]] == -1)
		{
			anc2[color2[i]] = i;
			sk[color2[i]] = i;
			ogt[color1[i]] = 1;
		}
		else if(ogt[color1[i]] == 0)
		{
			ans[i][anc2[color2[i]]] = 1;
			ans[anc2[color2[i]]][i] = 1;
			anc2[color2[i]] = i;
			ogt[color1[i]] = 1;
			vra[color2[i]] = i;
		}
	}
	for ( i = 0; i <= n; i++)
	{
		if (qan[i] > 2)
		{
			ans[ska[i]][vra[i]] = 1;
			ans[vra[i]][ska[i]] = 1;
		}
	}
	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:38:26: warning: unused variable 'st' [-Wunused-variable]
   38 |  int n = x.size(), i, j, st = 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