Submission #497130

#	Time	Username	Problem	Language	Result	Execution time	Memory
497130		Hanksburger	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	208 ms	24060 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > grp, ans;
bool visited[1005];
vector<int> tmp;
queue<int> Q;
int construct(vector<vector<int> > P)
{
	int N=P.size();
	bool subtask1=1, subtask2=1;
	for (int i=0; i<N; i++)
	{
		for (int j=0; j<N; j++)
		{
			if (P[i][j]==0 || P[i][j]==2 || P[i][j]==3)
				subtask1=0;
			if (P[i][j]==2 || P[i][j]==3)
				subtask2=0;
		}
	}
	if (subtask1)
	{
		tmp.push_back(0);
		for (int i=1; i<N; i++)
			tmp.push_back(1);
		ans.push_back(tmp);
		for (int i=1; i<N; i++)
		{
			tmp.clear();
			tmp.push_back(1);
			for (int j=1; j<N; j++)
				tmp.push_back(0);
			ans.push_back(tmp);
		}
	}
	else
	{
		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++)
		{
			tmp.clear();
			for (int j=0; j<N; j++)
				tmp.push_back(0);
			ans.push_back(tmp);
		}
		for (int i=0; i<grp.size(); i++)
		{
			for (int j=1; j<grp[i].size(); j++)
			{
				int u=grp[i][j-1], v=grp[i][j];
				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:63:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for (int i=0; i<grp.size(); i++)
      |                 ~^~~~~~~~~~~
supertrees.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |    for (int j=0; j<grp[i].size(); j++)
      |                  ~^~~~~~~~~~~~~~
supertrees.cpp:68:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (int k=j+1; k<grp[i].size(); k++)
      |                     ~^~~~~~~~~~~~~~
supertrees.cpp:80:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |   for (int i=0; i<grp.size(); i++)
      |                 ~^~~~~~~~~~~
supertrees.cpp:82:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |    for (int j=1; j<grp[i].size(); j++)
      |                  ~^~~~~~~~~~~~~~
supertrees.cpp:11:19: warning: variable 'subtask2' set but not used [-Wunused-but-set-variable]
   11 |  bool subtask1=1, subtask2=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