제출 #693045

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
693045		NemanjaSo2005	슈퍼트리 잇기 (IOI20_supertrees)	C++14	11 / 100	204 ms	24068 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];
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];
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++){
      if(getparent(i)!=i)
         continue;
      tclik.clear();
      tclik.push_back(i);
      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(i,j);
         }
      }
      if(tclik.size()==1)
         continue;
      tclik.push_back(i);
      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=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;
}

컴파일 시 표준 에러 (stderr) 메시지

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |          for(int k=0;k<tclik.size();k++){
      |                      ~^~~~~~~~~~~~~
supertrees.cpp:66:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |       for(int j=0;j<tclik.size()-1;j++){
      |                   ~^~~~~~~~~~~~~~~
supertrees.cpp:90:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |    for(int i=0;i<p.size();i++)
      |                ~^~~~~~~~~
supertrees.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |       for(int j=0;j<p.size();j++)
      |                   ~^~~~~~~~~
supertrees.cpp:94:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |       for(int j=0;j<graf[i].size();j++)
      |                   ~^~~~~~~~~~~~~~~

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