Submission #497140

#	Time	Username	Problem	Language	Result	Execution time	Memory
497140		Hanksburger	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	234 ms	24008 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > grp, subgrp, ans;
bool visited[1005];
vector<int> tmp;
queue<int> Q;
int construct(vector<vector<int> > P)
{
	int N=P.size();
	for (int i=0; i<N; i++)
		for (int j=i+1; j<N; j++)
			if (P[i][j]==3)
				return 0;
	for (int i=0; i<N; i++)
	{
		tmp.clear();
		for (int j=0; j<N; j++)
			tmp.push_back(0);
		ans.push_back(tmp);
	}
	for (int i=0; i<N; i++)
	{
		if (visited[i])
			continue;
		tmp.clear();
		tmp.push_back(i);
		Q.push(i);
		visited[i]=1;
		while (!Q.empty())
		{
			int u=Q.front();
			Q.pop();
			for (int j=0; j<N; j++)
			{
				if (P[u][j] && !visited[j])
				{
					tmp.push_back(j);
					Q.push(j);
					visited[j]=1;
				}
			}
		}
		grp.push_back(tmp);
	}
	for (int i=0; i<grp.size(); i++)
	{
		for (int j=0; j<grp[i].size(); j++)
		{
			int u=grp[i][j];
			for (int k=j+1; k<grp[i].size(); k++)
				if (!P[u][grp[i][k]])
					return 0;
		}
	}
	for (int i=0; i<N; i++)
		visited[i]=0;
	for (int i=0; i<grp.size(); i++)
	{
		subgrp.clear();
		for (int j=0; j<grp[i].size(); j++)
		{
			int x=grp[i][j];
			if (visited[x])
				continue;
			tmp.clear();
			tmp.push_back(x);
			Q.push(x);
			visited[x]=1;
			while (!Q.empty())
			{
				int u=Q.front();
				Q.pop();
				for (int k=0; k<N; k++)
				{
					if (P[u][k]==1 && !visited[k])
					{
						tmp.push_back(k);
						Q.push(k);
						visited[k]=1;
					}
				}
			}
			subgrp.push_back(tmp);
		}
		if (subgrp.size()==2)
			return 0;
		for (int j=0; j<subgrp.size(); j++)
		{
			for (int k=0; k<subgrp[j].size(); k++)
			{
				int u=subgrp[j][k];
				for (int l=k+1; l<subgrp[j].size(); l++)
					if (P[u][subgrp[j][l]]==2)
						return 0;
			}
		}
		for (int j=0; j<subgrp.size(); j++)
		{
			for (int k=1; k<subgrp[j].size(); k++)
			{
				int u=subgrp[j][k-1], v=subgrp[j][k];
				ans[u][v]=ans[v][u]=1;
			}
		}
		if (subgrp.size()>=3)
		{
			for (int j=1; j<subgrp.size(); j++)
			{
				int u=subgrp[j-1][0], v=subgrp[j][0];
				ans[u][v]=ans[v][u]=1;
			}
			int u=subgrp[0][0], v=subgrp[subgrp.size()-1][0];
			ans[u][v]=ans[v][u]=1;
		}
	}
	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:46:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |  for (int i=0; i<grp.size(); i++)
      |                ~^~~~~~~~~~~
supertrees.cpp:48:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for (int j=0; j<grp[i].size(); j++)
      |                 ~^~~~~~~~~~~~~~
supertrees.cpp:51:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |    for (int k=j+1; k<grp[i].size(); k++)
      |                    ~^~~~~~~~~~~~~~
supertrees.cpp:58:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for (int i=0; i<grp.size(); i++)
      |                ~^~~~~~~~~~~
supertrees.cpp:61:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for (int j=0; j<grp[i].size(); j++)
      |                 ~^~~~~~~~~~~~~~
supertrees.cpp:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |   for (int j=0; j<subgrp.size(); j++)
      |                 ~^~~~~~~~~~~~~~
supertrees.cpp:90:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |    for (int k=0; k<subgrp[j].size(); k++)
      |                  ~^~~~~~~~~~~~~~~~~
supertrees.cpp:93:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int l=k+1; l<subgrp[j].size(); l++)
      |                     ~^~~~~~~~~~~~~~~~~
supertrees.cpp:98:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |   for (int j=0; j<subgrp.size(); j++)
      |                 ~^~~~~~~~~~~~~~
supertrees.cpp:100:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |    for (int k=1; k<subgrp[j].size(); k++)
      |                  ~^~~~~~~~~~~~~~~~~
supertrees.cpp:108:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |    for (int j=1; j<subgrp.size(); j++)
      |                  ~^~~~~~~~~~~~~~

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