Submission #589740

#	Time	Username	Problem	Language	Result	Execution time	Memory
589740		LIF	Connecting Supertrees (IOI20_supertrees)	C++14	40 / 100	223 ms	28036 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;
	bool flagy = 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(p[i][j]!=0 &&p[i][j]!=2)
			{
				if(i==j)continue;
				flagy = 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;
							}
						}
					}	
				}
			}
		}
		else
		{
			if(flagy == 1)//that means the distance are all 0 or 2; 
			{
				for(int i=0;i<n;i++)
				{
					for(int j=i+1;j<n;j++)
					{
						if(find(i)!=find(j))
						{
							if(p[i][j] == 0)continue;
							else//they have the way to go each other.
							{
								for(int kk=0;kk<n;kk++)
								{
									if(find(kk) == find(i))
									{
										if(p[kk][j] == 0)
										{
											return 0;
											break;
										}	
									}
								
								}
							}
							f[find(j)] = find(i);
						}
						else //they means they have same father
						{
							if(p[i][j] == 0) //it is impossible
							{
								return 0;
								break;
							}
						}
					}
				}
				
				vector<int> nod[1005];
				for(int i=0;i<n;i++)
				{
					int xx = find(i);
					nod[xx].push_back(i);
				}
				for(int i=0;i<n;i++)
				{
					if(nod[i].size()!=0)
					{
						if(nod[i].size()==2)
						{
							return 0;
							break;
						}
						else
						{
							for(int j=0;j<nod[i].size()-1;j++)
							{
								int xx = nod[i][j];
								int yy = nod[i][j+1];
							
								checkx[xx][yy]= true;
								checkx[yy][xx] = true;
							}
							int m = nod[i].size();
							int xx = nod[i][m-1];
							int yy = nod[i][0];
							checkx[xx][yy] = true;
							checkx[yy][xx] = true;
						}
					}
				}
			}
			
		}
	}
		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:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int i=0;i<p[0].size()-1;i++)
      |               ~^~~~~~~~~~~~~~
supertrees.cpp:165:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |        for(int j=0;j<nod[i].size()-1;j++)
      |                    ~^~~~~~~~~~~~~~~~
supertrees.cpp:185:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |   for(int i=0;i<p[0].size();i++)
      |               ~^~~~~~~~~~~~
supertrees.cpp:188:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  188 |    for(int j=0;j<p[0].size();j++)
      |                ~^~~~~~~~~~~~

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