Submission #589632

#	Time	Username	Problem	Language	Result	Execution time	Memory
589632		LIF	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	222 ms	27928 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
int checkx[1005][1005];
int f[1005];
int find(int x)
{
	if(f[x] == x)
	{
		return x;
	}
	return f[x] = find(f[x]);
}
int construct(std::vector<std::vector <int> > p) {
	int n = p[0].size();
	for(int i=0;i<n;i++)
	{
		f[i] = i;
	}
	bool flag = 1;
	bool flagk = 1;
	vector <vector<int> > ans;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(p[i][j] == 3)
			{
				return 0;
			}
			if(p[i][j]!=1)
			{
				flag = 0; 
			}
			if(p[i][j] !=0&&p[i][j]!=1)
			{
				flagk = 0;
			}
		}
	}
	if(flag == 1) //that means all distance is 1;
	{
		for(int i=0;i<p[0].size()-1;i++)
		{
			checkx[i][i+1] = true;
			checkx[i+1][i] = true;	
		}
	}
	else
	{
		if(flagk == 1)//that means all distance is 0 or 1;
		{
			for(int i=0;i<n;i++)
			{
				for(int j=i+1;j<n;j++)
				{
					if(find(i)!=find(j))
					{
						if(p[i][j] == 1)
						{
							int xx = find(i);
							for(int kk=0;kk<n;kk++)
							{
								if(find(kk) == xx) //that means they are in the same group
								{
									if(p[xx][j]==0) //that means they can't go to each other,however their father can go to each other.it can't be implented 
									{
										return 0;
										break;
									}
								}
							}
							//if it hasn't return,that means it can be implented.
							checkx[i][j] = true;
							checkx[j][i] = true;	
							//and we should add the j in the same group;
							f[find(j)] = find(i);
						}
						else
						{
							continue;
						}
					}
					else//that means they are in the same set.
					{
						if(p[i][j] == 1)
						{
							continue;
						} 
						else
						{
							if(p[i][j] == 0)
							{
								return 0;
								break;
							}
						}
					}
				
				}
			}
		}
	}
	for(int i=0;i<p[0].size();i++)
	{
		vector<int> v;
		for(int j=0;j<p[0].size();j++)
		{
			if(i==j)
			{
				v.push_back(0);
			}
			else
			{
				if(checkx[i][j] == true)
				{
					v.push_back(1);
				}
				else
				{
					v.push_back(0);
				}
			}
		}
			ans.push_back(v);		
	}
	build(ans);
	return 1;
}

Compilation message (stderr)

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

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