Submission #601199

#	Time	Username	Problem	Language	Result	Execution time	Memory
601199		yutabi	Connecting Supertrees (IOI20_supertrees)	C++14	96 / 100	235 ms	24000 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;


#define pb push_back


int construct(std::vector<std::vector<int>> p)
{
	int n = p.size();

	std::vector<std::vector<int>> answer(n,vector <int> (n,0));

	vector <bool> v(n,0);

	vector <vector <int> > graphs;

	for(int i=0;i<n;i++)
	{
		if(v[i]==0)
		{
			graphs.pb({});

			stack <int> st;

			st.push(i);

			while(st.size())
			{
				int node=st.top();
				st.pop();

				v[node]=1;
				graphs.back().pb(node);

				for(int j=0;j<n;j++)
				{
					if(node!=j && p[node][j]>0 && v[j]==0)
					{
						st.push(j);
						v[j]=1;
					}
				}
			}
		}
	}

	for(int i=0;i<graphs.size();i++)
	{
		for(int j=0;j<graphs[i].size();j++)
		{
			for(int k=j+1;k<graphs[i].size();k++)
			{
				if(p[graphs[i][j]][graphs[i][k]]==0)
				{
					return 0;
				}
			}
		}

		int val=-1;

		for(int j=0;j<graphs[i].size();j++)
		{
			for(int k=j+1;k<graphs[i].size();k++)
			{
				int nw=p[graphs[i][j]][graphs[i][k]];

				if(nw==2)
				{
					if(val==3)
					{
						return 0;
					}

					val=2;
				}

				if(nw==3)
				{
					if(val==2)
					{
						return 0;
					}

					val=3;
				}
			}
		}

		vector <vector <int> > trees;

		v=vector <bool> (graphs[i].size(),0);

		for(int j=0;j<graphs[i].size();j++)
		{
			if(v[j]==0)
			{
				trees.pb({});

				stack <int> st;

				st.push(j);

				while(st.size())
				{
					int node=st.top();
					st.pop();

					v[node]=1;
					trees.back().pb(graphs[i][node]);

					for(int k=0;k<graphs[i].size();k++)
					{
						if(node!=k && p[graphs[i][node]][graphs[i][k]]==1 && v[k]==0)
						{
							st.push(k);
							v[k]=1;
						}
					}
				}
			}
		}

		if(trees.size()==2)
		{
			return 0;
		}

		if(val==3 && trees.size()==3)
		{
			return 0;
		}

		for(int j=0;j<trees.size();j++)
		{
			for(int k=0;k<trees[j].size();k++)
			{
				for(int l=k+1;l<trees[j].size();l++)
				{
					if(p[trees[j][k]][trees[j][l]]!=1)
					{
						return 0;
					}
				}
			}
		}

		for(int j=0;j<trees.size();j++)
		{
			for(int k=0;k+1<trees[j].size();k++)
			{
				answer[trees[j][k]][trees[j][k+1]]=1;
				answer[trees[j][k+1]][trees[j][k]]=1;
			}

			answer[trees[(j)%trees.size()][0]][trees[(j+1)%trees.size()][0]]=1;
			answer[trees[(j+1)%trees.size()][0]][trees[(j)%trees.size()][0]]=1;
		}

		if(val==3)
		{
			answer[trees[0][0]][trees[2][0]]=1;
			answer[trees[2][0]][trees[0][0]]=1;
		}
	}

	for(int i=0;i<n;i++)
	{
		answer[i][i]=0;
	}

	build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i=0;i<graphs.size();i++)
      |              ~^~~~~~~~~~~~~~
supertrees.cpp:51:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |   for(int j=0;j<graphs[i].size();j++)
      |               ~^~~~~~~~~~~~~~~~~
supertrees.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |    for(int k=j+1;k<graphs[i].size();k++)
      |                  ~^~~~~~~~~~~~~~~~~
supertrees.cpp:64:16: 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<graphs[i].size();j++)
      |               ~^~~~~~~~~~~~~~~~~
supertrees.cpp:66:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |    for(int k=j+1;k<graphs[i].size();k++)
      |                  ~^~~~~~~~~~~~~~~~~
supertrees.cpp:96:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |   for(int j=0;j<graphs[i].size();j++)
      |               ~^~~~~~~~~~~~~~~~~
supertrees.cpp:114:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |      for(int k=0;k<graphs[i].size();k++)
      |                  ~^~~~~~~~~~~~~~~~~
supertrees.cpp:136:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |   for(int j=0;j<trees.size();j++)
      |               ~^~~~~~~~~~~~~
supertrees.cpp:138:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |    for(int k=0;k<trees[j].size();k++)
      |                ~^~~~~~~~~~~~~~~~
supertrees.cpp:140:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     for(int l=k+1;l<trees[j].size();l++)
      |                   ~^~~~~~~~~~~~~~~~
supertrees.cpp:150:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |   for(int j=0;j<trees.size();j++)
      |               ~^~~~~~~~~~~~~
supertrees.cpp:152:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |    for(int k=0;k+1<trees[j].size();k++)
      |                ~~~^~~~~~~~~~~~~~~~

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