Submission #1078826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078826		Muhammad_Aneeq	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	127 ms	24148 KiB

supertrees

#include <vector>
#include <iostream>
using namespace std;
int const MAXN=1000;
void build(vector<vector<int>> b);
int construct(vector<vector<int>> p)
{
	int n=p.size();
	bool seen[n]={};
	int head[n]={};
	bool vis[n]={};
	vector<vector<int>>b(n,vector<int>(n,0));
	for (int i=0;i<n;i++)
	{
		if (!seen[i])
		{
			seen[i]=1;
			head[i]=i;
			for (int j=0;j<n;j++)
			{
				if (seen[j])
				{
					if (i!=j&&p[i][j]==1)
						return 0;
					continue;
				}
				if (p[i][j]==1)
				{
					seen[j]=1;
					b[i][j]=b[j][i]=1;
					head[j]=i;
				}
			}
		}
	}
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<n;j++)
		{
			if (p[i][j]==1&&head[i]!=head[j])
				return 0;
			if (p[i][j]!=1&&head[i]==head[j])
				return 0;
		}
	}
	for (int i=0;i<n;i++)
	{
		if (vis[head[i]])
			continue;
		vector<int>x;
		for (int j=0;j<n;j++)
		{
			if (p[i][j]&&!vis[head[j]])
			{
				x.push_back(head[j]);
				vis[head[j]]=1;
			}
		}
		if (x.size()==2)
			return 0;
		if (x.size()<2)
			continue;
		int pa=head[i];
		for (int  j=0;j<x.size();j++)
		{
			int u=x[j],v=x[(j+1)%x.size()];
			head[u]=head[v]=pa;
			b[u][v]=b[v][u]=1;
		}
	}
	for (int i=0;i<n;i++)
	{
		for (int j=0;j<n;j++)
		{
			int u=head[head[i]],v=head[head[j]];
			if (u==v)
				continue;
			if (p[i][j]==0&&b[u][v])
				return 0;
			if (p[i][j]==2&&!b[u][v])
				return 0;
		}
	}
	build(b);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for (int  j=0;j<x.size();j++)
      |                 ~^~~~~~~~~

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