Submission #693079

#	Time	Username	Problem	Language	Result	Execution time	Memory
693079		NemanjaSo2005	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	1 ms	340 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],rod1[1005],vel1[1005],boja[1005],bk[1005],niz[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;
}
int getparent1(int koji){
   if(rod1[koji]==koji)
      return koji;
   rod1[koji]=getparent1(rod1[koji]);
   return rod1[koji];
}
void spoj1(int a,int b){
   a=getparent1(a);
   b=getparent1(b);
   if(vel1[a]<vel1[b])
      rod1[a]=b;
   else{
      vel1[a]=max(vel1[a],vel1[b]+1);
      rod1[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;
}
bool cmp(int a,int b){
   return bk[a]>bk[b];
}
int construct(vector<vector<int>> p){
   N=p.size();
   for(int i=1;i<=N;i++){
      rod[i]=i;
      vel[i]=1;
      rod1[i]=i;
      vel1[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]==1){
            bk[i]++;
            bk[j]++;
         }
         if(kol[i][j]==3)
            return 0;
      }
   for(int i=1;i<=N;i++)
      for(int j=i+1;j<=N;j++)
         if(kol[i][j]==1)
            spoj1(i,j);
   for(int i=1;i<=N;i++)
      niz[i]=i;
   //sort(niz+1,niz+1+N,cmp);
   for(int i=1;i<=N;i++){
      int tren=niz[i];
      if(getparent(tren)!=tren)
         continue;
      tclik.clear();
      tclik.push_back(tren);
      for(int j=1;j<=N;j++){
         if(getparent(j)!=j)
            continue;
         bool moze=true;
         for(int k=0;k<tclik.size();k++){
            if(kol[j][tclik[k]]!=2)
               moze=false;
         /*   if(getparent1(j)==getparent1(tclik[k]))
               moze=false;*/
         }
         if(moze){
            tclik.push_back(j);
          //  spoj(tren,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 i=1;i<=N;i++)
      for(int j=1;j<=N;j++){
        // cout<<i<<" "<<j<<endl;
       //  if(getparent(i)==getparent(j))
         //   continue;
        // cout<<"X"<<endl;
         if(kol[i][j]!=1)
            continue;
        // cout<<"Y"<<endl;
         if(stavio[i] and stavio[j]){
  //          cout<<i<<" "<<j<<endl;
            return 0;
         }
         //cout<<"SPOJ"<<endl;
         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]){
            //cout<<"A"<<endl;
            return 0;
         }
         if(kol[i][j]==0 and boja[i]==boja[j]){
            //cout<<"B"<<endl;
            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:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    for(int i=0;i<graf[gde].size();i++)
      |                ~^~~~~~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |          for(int k=0;k<tclik.size();k++){
      |                      ~^~~~~~~~~~~~~
supertrees.cpp:102:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |       for(int j=0;j<tclik.size()-1;j++){
      |                   ~^~~~~~~~~~~~~~~
supertrees.cpp:145:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |    for(int i=0;i<p.size();i++)
      |                ~^~~~~~~~~
supertrees.cpp:146:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |       for(int j=0;j<p.size();j++)
      |                   ~^~~~~~~~~
supertrees.cpp:149:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |       for(int j=0;j<graf[i].size();j++)
      |                   ~^~~~~~~~~~~~~~~

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