Submission #693118

#	Time	Username	Problem	Language	Result	Execution time	Memory
693118		NemanjaSo2005	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	211 ms	24100 KiB

supertrees

#include<bits/stdc++.h>
#include "supertrees.h"
#define ll long long
using namespace std;
int kol[1005][1005],N,rod[1005],vel[1005],boja[1005];
vector<int> tclik;
bool stavio[1005];
int getparent(int koji){
   if(rod[koji]==koji)
      return koji;
   rod[koji]=getparent(rod[koji]);
   return rod[koji];
}
void spoj(int a,int b){
   a=getparent(a);
   b=getparent(b);
   if(vel[a]<vel[b])
      rod[a]=b;
   else{
      vel[a]=max(vel[a],vel[b]+1);
      rod[b]=a;
   }
   return;
}
vector<int> graf[1005];
void dfs(int gde,int stavi){
   boja[gde]=stavi;
   for(int i=0;i<graf[gde].size();i++)
      if(boja[graf[gde][i]]==0)
         dfs(graf[gde][i],stavi);
   return;
}
int construct(vector<vector<int>> p){
   N=p.size();
   for(int i=1;i<=N;i++){
      rod[i]=i;
      vel[i]=1;
   }
   for(int i=1;i<=N;i++)
      for(int j=1;j<=N;j++){
         kol[i][j]=p[i-1][j-1];
         if(kol[i][j]==3)
            return 0;
      }

   for(int i=1;i<=N;i++){
      int tren=i;
      if(stavio[tren])
         continue;
      if(graf[tren].size()!=0)
        continue;
      tclik.clear();
      tclik.push_back(tren);
      for(int j=1;j<=N;j++){
         if(j==i)
            continue;
         if(stavio[j])
            continue;
         bool moze=true;
         for(int k=0;k<tclik.size();k++)
            if(kol[j][tclik[k]]!=2)
               moze=false;
         if(moze)
            tclik.push_back(j);
      }
      if(tclik.size()<=2)
         continue;
      tclik.push_back(tren);
      for(int j=0;j<tclik.size()-1;j++){
         spoj(tren,tclik[j]);
         graf[tclik[j]].push_back(tclik[j+1]);
         graf[tclik[j+1]].push_back(tclik[j]);
         stavio[tclik[j]]=true;
      }/*
      cout<<"KLIK OD "<<i<<":\n";
      for(int j=0;j<tclik.size();j++)
         cout<<tclik[j]<<" ";
      cout<<endl;*/
      for(int j=0;j<tclik.size()-1;j++){
         int tmp=tclik[j];
         for(int k=1;k<=N;k++){
            if(getparent(k)==getparent(tmp))
               continue;
            if(kol[tmp][k]!=1)
               continue;
            if(stavio[k])
               return 0;
            spoj(tmp,k);
            graf[tmp].push_back(k);
            graf[k].push_back(tmp);
         }
      }
   }

   for(int i=1;i<=N;i++){
      for(int j=1;j<=N;j++)
         if(kol[i][j]==1 and getparent(i)!=getparent(j)){
            spoj(i,j);
            graf[i].push_back(j);
            graf[j].push_back(i);
         }
   }

   for(int i=1;i<=N;i++)
      if(boja[i]==0)
         dfs(i,i);
   for(int i=1;i<=N;i++)
      for(int j=1;j<=N;j++){
         if(kol[i][j]!=0 and boja[i]!=boja[j]){
            return 0;
         }
         if(kol[i][j]==0 and boja[i]==boja[j]){
            return 0;
         }
      }
   for(int i=0;i<p.size();i++)
      for(int j=0;j<p.size();j++)
         p[i][j]=0;
   for(int i=1;i<=N;i++)
      for(int j=0;j<graf[i].size();j++)
         p[i-1][graf[i][j]-1]=1;
   build(p);
   return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'void dfs(int, int)':
supertrees.cpp:28:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    for(int i=0;i<graf[gde].size();i++)
      |                ~^~~~~~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |          for(int k=0;k<tclik.size();k++)
      |                      ~^~~~~~~~~~~~~
supertrees.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |       for(int j=0;j<tclik.size()-1;j++){
      |                   ~^~~~~~~~~~~~~~~
supertrees.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |       for(int j=0;j<tclik.size()-1;j++){
      |                   ~^~~~~~~~~~~~~~~
supertrees.cpp:116:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |    for(int i=0;i<p.size();i++)
      |                ~^~~~~~~~~
supertrees.cpp:117:20: 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 j=0;j<p.size();j++)
      |                   ~^~~~~~~~~
supertrees.cpp:120:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |       for(int j=0;j<graf[i].size();j++)
      |                   ~^~~~~~~~~~~~~~~

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