Submission #693059

#	Time	Username	Problem	Language	Result	Execution time	Memory
693059		NemanjaSo2005	Connecting Supertrees (IOI20_supertrees)	C++14	40 / 100	214 ms	22312 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],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;
}
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;
   }
   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++)
      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;
         int k1=0;
         bool moze=true;
         for(int k=0;k<tclik.size();k++){
            if(kol[j][tclik[k]]!=2)
               moze=false;
            if(kol[j][tclik[k]]==1)
               k1++;
         }
         if(k1>1){
            //cout<<"OVDE"<<endl;
            return 0;
         }
         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++){
         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++){
         if(getparent(i)==getparent(j))
            continue;
         if(kol[i][j]!=1)
            continue;
         if(stavio[i] and stavio[j]){
            cout<<i<<" "<<j<<endl;
            return 0;
         }
         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:66:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |          for(int k=0;k<tclik.size();k++){
      |                      ~^~~~~~~~~~~~~
supertrees.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |       for(int j=0;j<tclik.size()-1;j++){
      |                   ~^~~~~~~~~~~~~~~
supertrees.cpp:118:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |    for(int i=0;i<p.size();i++)
      |                ~^~~~~~~~~
supertrees.cpp:119:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |       for(int j=0;j<p.size();j++)
      |                   ~^~~~~~~~~
supertrees.cpp:122:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |       for(int j=0;j<graf[i].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