Submission #316365

#	Time	Username	Problem	Language	Result	Execution time	Memory
316365		demetre	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	279 ms	29432 KiB

supertrees

#include "supertrees.h"
#include <vector>
# include <bits/stdc++.h>
using namespace std;
 
long long par[300005],a,bb,n,fix[300005],w1,w2,sh1,fix1[300005],wv,par1[300005];
long long pa,sh;
//std::vector <std::vector <int> >  ans;
vector <long long> v[300005],v1,v2;
int get_col(int a)
{
    if (par[a]==a) return a;
    par[a]=get_col(par[a]);
    return par[a];
}
void col(int a, int b)
{
    a=get_col(a);
    b=get_col(b);
    par[a]=b;
}
int get_col1(int a)
{
    if (par1[a]==a) return a;
    par1[a]=get_col1(par1[a]);
    return par1[a];
}
void col1(int a, int b)
{
    a=get_col1(a);
    b=get_col1(b);
    par1[a]=b;
}
int construct(vector <vector <int> > p)
{
     int n=p.size();
     for (int i=0; i<n; i++)
   {
          par[i]=i;
     }
     for (int i=0; i<n; i++)
     {
          for (int j=0; j<n; j++)
          {
               if (p[i][j]==3)
               return 0;
          }
     }
     for (int i=0; i<n; i++)
    {
          for (int j=0; j<n; j++)
          {
               if (p[i][j]) col(i,j);
          }
     }
     for (int i=0; i<n; i++)
     {
         for (int j=0; j<n; j++)
         {
             if (get_col(i)==get_col(j) && !p[i][j]) return 0;
         }
     }
     
     for (int i=0; i<n;i++)
     {
          v[get_col(i)].push_back(i);
     }
     for (int i=0; i<n; i++)
     {
        if (!fix[get_col(i)])
        {
            v1.push_back(get_col(i)); 
            fix[get_col(i)]=1;              
        }
     }
	vector < vector < int > > ans(n, vector < int >(n, 0));
	for (int i=0; i<n; i++)
	{
		par1[i]=i;
	}
     for (int i=0; i<v1.size(); i++)
     {
     	pa=v1[i];
     	for(int j=0;j<v[pa].size(); j++)
     	{
     		for (int j1=j+1; j1<v[pa].size(); j1++)
     		{
     			w1=v[pa][j];
     			w2=v[pa][j1];
     			if (p[w1][w2]==1)
     			col1(w1,w2);
			}
		}
	}
	for (int i=0; i<v1.size() ;i++)
	{
		pa=v1[i];
		for(int j=0; j<v[pa].size(); j++)
		{
			sh=get_col1(v[pa][j]);
			sh1=v[pa][j];
			if (sh!=sh1)
			{
				ans[sh][sh1]=1;
				ans[sh1][sh]=1;
			}
		}
	}
	/*
4 
1 1 2 2 
1 1 2 2
2 2 1 2
2 2 2 1
	*/
    for (int i=0; i<v1.size(); i++)
    {
    		pa=v1[i];
    		for (int j=0; j<v[pa].size(); j++)
    		{
    			for (int j1=0; j1<v[pa].size(); j1++)
			{
				w1=v[pa][j];
     			w2=v[pa][j1];
     			if (p[w1][w2]==2)
     			{
     				if (get_col1(w1)==get_col1(w2)) return 0;
				}
			}
		}
    }
    for (int i=0; i<v1.size(); i++)
    {
    		pa=v1[i];
    		v2.clear();
    		for (int j=0; j<v[pa].size(); j++)
    		{
    			wv=v[pa][j];
    			if (!fix1[get_col1(wv)])
			{
				fix1[get_col1(wv)]=1;
				v2.push_back(get_col1(wv));    	
			}
		}
		if (v2.size()==2)
		{
			return 0;
		}
		v2.push_back(v2[0]);
		for (int i=1; i<v2.size(); i++)
		{
			w1=v2[i];
			w2=v2[i-1];
			if (w1!=w2)
			{
			
			ans[w1][w2]=1;
			ans[w2][w1]=1;
			}
		}
    }
    
     build(ans);
  return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:81:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |      for (int i=0; i<v1.size(); i++)
      |                    ~^~~~~~~~~~
supertrees.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |       for(int j=0;j<v[pa].size(); j++)
      |                   ~^~~~~~~~~~~~~
supertrees.cpp:86:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |        for (int j1=j+1; j1<v[pa].size(); j1++)
      |                         ~~^~~~~~~~~~~~~
supertrees.cpp:95:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |  for (int i=0; i<v1.size() ;i++)
      |                ~^~~~~~~~~~
supertrees.cpp:98:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |   for(int j=0; j<v[pa].size(); j++)
      |                ~^~~~~~~~~~~~~
supertrees.cpp:116:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |     for (int i=0; i<v1.size(); i++)
      |                   ~^~~~~~~~~~
supertrees.cpp:119:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |       for (int j=0; j<v[pa].size(); j++)
      |                     ~^~~~~~~~~~~~~
supertrees.cpp:121:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |        for (int j1=0; j1<v[pa].size(); j1++)
      |                       ~~^~~~~~~~~~~~~
supertrees.cpp:132:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for (int i=0; i<v1.size(); i++)
      |                   ~^~~~~~~~~~
supertrees.cpp:136:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |       for (int j=0; j<v[pa].size(); j++)
      |                     ~^~~~~~~~~~~~~
supertrees.cpp:150:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |   for (int i=1; i<v2.size(); i++)
      |                 ~^~~~~~~~~~

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