Submission #497135

#	Time	Username	Problem	Language	Result	Execution time	Memory
497135		Hanksburger	슈퍼트리 잇기 (IOI20_supertrees)	C++17	40 / 100	195 ms	24064 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, subtask3=1;
	for (int i=0; i<N; i++)
	{
		for (int j=i+1; 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 (P[i][j]==1 || P[i][j]==3)
				subtask3=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 if (subtask2)
	{
		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;
			}
		}
	}
	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++)
		{
			if (grp[i].size()==2)
				return 0;
			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;
			}
			if (grp[i].size()>=3)
			{
				int u=grp[i][0], v=grp[i][grp[i].size()-1];
				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:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for (int i=0; i<grp.size(); i++)
      |                 ~^~~~~~~~~~~
supertrees.cpp:67:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |    for (int j=0; j<grp[i].size(); j++)
      |                  ~^~~~~~~~~~~~~~
supertrees.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int k=j+1; k<grp[i].size(); k++)
      |                     ~^~~~~~~~~~~~~~
supertrees.cpp:82:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |   for (int i=0; i<grp.size(); i++)
      |                 ~^~~~~~~~~~~
supertrees.cpp:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |    for (int j=1; j<grp[i].size(); j++)
      |                  ~^~~~~~~~~~~~~~
supertrees.cpp:117:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |   for (int i=0; i<grp.size(); i++)
      |                 ~^~~~~~~~~~~
supertrees.cpp:121:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |    for (int j=0; j<grp[i].size(); j++)
      |                  ~^~~~~~~~~~~~~~
supertrees.cpp:124:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |     for (int k=j+1; k<grp[i].size(); k++)
      |                     ~^~~~~~~~~~~~~~
supertrees.cpp:136:18: 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 i=0; i<grp.size(); i++)
      |                 ~^~~~~~~~~~~
supertrees.cpp:138:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |    for (int j=1; j<grp[i].size(); j++)
      |                  ~^~~~~~~~~~~~~~
supertrees.cpp:11:31: warning: variable 'subtask3' set but not used [-Wunused-but-set-variable]
   11 |  bool subtask1=1, subtask2=1, subtask3=1;
      |                               ^~~~~~~~

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