Submission #590069

#	Time	Username	Problem	Language	Result	Execution time	Memory
590069		LIF	Connecting Supertrees (IOI20_supertrees)	C++14	40 / 100	272 ms	28028 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;
	bool flagall = 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(p[i][j]!=0&&p[i][j]!=1&&p[i][j]!=2)
			{
				flagall = 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;
						}
					}
				}
			}
			else //that means they are all 0,1,2;
			{
				if(flagall == 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] == 0)continue;
								//that means they are some ways to go.
								for(int kk=0;kk<n;kk++)
								{
									if(find(kk) == find(i)) //that means they are in the same group
									{
										if(p[kk][j] == 0)
										{
											return 0;
											break;
										}
									}
								}
								f[find(j)] = find(i);
							}
							else //that means they are in the same group
							{
								if(p[i][j] == 0) //that means they are in the same group,but no ways to go to each other
								{
									return 0;
									break;
								} 	
							}
						}
					}
					//and we can know the different kinds of node.
					vector<int> nod[1005];
					for(int i=0;i<n;i++)
					{
						int xx = find(i);
						nod[xx].push_back(i);
					}
					//reset the merge and query set.
					for(int i=0;i<n;i++)
					{
						f[i] = i;
					}
					vector<int> edge[1005]; 
					
					for(int i=0;i<n;i++)
					{
						for(int j=0;j<n;j++)
						{
							edge[j].clear();
						}
						if(nod[i].size() == 0||nod[i].size()==1)continue;
						for(int j=0;j<nod[i].size();j++)
						{
							int xx = nod[i][j];
							edge[xx].push_back(xx);
						}
						for(int j=0;j<nod[i].size();j++)
						{
							for(int k=j+1;k<nod[i].size();k++)
							{
								if(p[j][k] == 0)return 0;
								else
								{
									if(find(j) !=find(k)) //that means they are not in the same edge.
									{
										if(p[j][k] == 1)
										{
											int temp = find(j);
											for(int pp=0;pp<edge[temp].size();pp++)
											{
												if(p[pp][k] == 2)return 0;
											}
											edge[temp].push_back(k);
											edge[k].pop_back();
											checkx[j][k] = true;
											checkx[k][j] = true;
											f[find(k)] = find(j);
										}
										else//that means p[j][k] = 2
										{
											int temp = find(j);
											for(int pp=0;pp<edge[temp].size();pp++)
											{
												if(p[pp][k] == 1) //if only one ways;
												{
													return 0;
												}
											}
										}
									}
									else //they are in the same group
									{
										if(p[j][k] == 2)return 0; //in the same group ,there mustn't be two ways.
										 
									}				
								}
							}
						}
						vector<int> pq;
						//and, we have finished disclpined all of the edge. 
						pq.clear();
						for(int j=0;j<n;j++)
						{
							if(edge[j].size()!=0)//it is for this set.
							{
								pq.push_back(edge[j][0]);
							}
						}
						if(pq.size()==2)//that means the count of edge is 2
						{
							vector<int> x1;
							for(int j=0;j<n;j++)
							{
								if(edge[j].size()!=0)
								{
									x1.push_back(j);
								}
							}
							int k1 = x1[0];
							int k2 = x1[1];
							for(int j=0;j<edge[k1].size();j++)
							{
								for(int k=0;k<edge[k2].size();k++)
								{
									int fst = edge[k1][j];
									int sd = edge[k2][k];
									if(p[fst][sd] == 2)
									{
										return 0;
									}
								}
							}
						}
						
						for(int j=0;j<pq.size()-1;j++)
						{
							int fst = pq[j];
							int sd = pq[j+1];
							checkx[fst][sd] = true;
							checkx[sd][fst] = true;
						}
						int m = pq.size();
						int fst = pq[0];
						int sd = pq[m-1];
						checkx[fst][sd] = true;
						checkx[sd][fst] = 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:56:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for(int i=0;i<p[0].size()-1;i++)
      |               ~^~~~~~~~~~~~~~
supertrees.cpp:171:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |        for(int j=0;j<nod[i].size()-1;j++)
      |                    ~^~~~~~~~~~~~~~~~
supertrees.cpp:244:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  244 |       for(int j=0;j<nod[i].size();j++)
      |                   ~^~~~~~~~~~~~~~
supertrees.cpp:249:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  249 |       for(int j=0;j<nod[i].size();j++)
      |                   ~^~~~~~~~~~~~~~
supertrees.cpp:251:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  251 |        for(int k=j+1;k<nod[i].size();k++)
      |                      ~^~~~~~~~~~~~~~
supertrees.cpp:261:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  261 |            for(int pp=0;pp<edge[temp].size();pp++)
      |                         ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:274:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  274 |            for(int pp=0;pp<edge[temp].size();pp++)
      |                         ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:313:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  313 |        for(int j=0;j<edge[k1].size();j++)
      |                    ~^~~~~~~~~~~~~~~~
supertrees.cpp:315:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  315 |         for(int k=0;k<edge[k2].size();k++)
      |                     ~^~~~~~~~~~~~~~~~
supertrees.cpp:327:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  327 |       for(int j=0;j<pq.size()-1;j++)
      |                   ~^~~~~~~~~~~~
supertrees.cpp:347:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  347 |   for(int i=0;i<p[0].size();i++)
      |               ~^~~~~~~~~~~~
supertrees.cpp:350:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  350 |    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