Submission #1190988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190988		Ak_16	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	123 ms	26112 KiB

supertrees

#include <iostream>
#include "supertrees.h"
#include <vector>
using namespace std;
int n;
int col[1005];
int ncol[1005];
int comp[1005];
int rep[1005][1005];
vector<vector<int>> b;


int construct(vector<vector<int>> p){
  n = p.size();
  int chk=1;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(p[i][j]==3) chk=0;
    }
  }
  
  
  if(chk==0){return 0;}
  
  
  b = p;
  
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      b[i][j]=0;
    }
  }
  
  int cnt=0;
  
  for(int i=0; i<n; i++){
    col[i]=0;
  }
  
  for(int i=0; i<n; i++){
    if(col[i]==0){
      cnt++;
      col[i]=cnt;
      for(int j=0; j<n; j++){
        if(j==i){continue;}
        
        if(p[i][j]>=1){
          col[j]=cnt;
        }
      }
    }
  }
  
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(p[i][j]==0&&col[i]==col[j]){chk=0; b[i][j]=0;}
      if(p[i][j]>=1&&col[i]!=col[j]){chk=0;}
    }
  }
  
  for(int i=0; i<n; i++){
    b[i][i]=0;
  }
  
  if(chk==0){return 0;}
  
  int ncnt=0;
  
  for(int i=0; i<n; i++){
    ncol[i]=0;
    comp[i]=0;
  }
  
  for(int i=0; i<n; i++){
    if(ncol[i]==0){
      ncnt++;
      ncol[i]=ncnt;
      comp[col[i]]++;
      rep[col[i]][comp[col[i]]]=i;
      
      for(int j=0; j<n; j++){
        if(j==i){continue;}
        
        if(p[i][j]==1){
          ncol[j]=ncnt;
        }
      }
    }
  }
  
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(p[i][j]==2&&ncol[i]==ncol[j]){chk=0;}
      if(p[i][j]==1&&ncol[i]!=ncol[j]){chk=0;}
    }
  }
  
  int don[1005];
  for(int i=0; i<n; i++){don[i]=0;}
  
  for(int i=0; i<n; i++){
    if(don[i]==0){
      for(int j=0; j<n; j++){
        if(ncol[i]==ncol[j]&&i!=j){
          b[i][j]=1;
          b[j][i]=1;
          don[j]=1;
        }
      }
    }
  }
  
  for(int i=1; i<=cnt; i++){
    if(comp[i]==2){chk=0;}
    
    if(comp[i]>=3){
      for(int j=1; j<comp[i]; j++){
        int n1 = rep[i][j];
        int n2 = rep[i][j+1];
        b[n1][n2]=1;
        b[n2][n1]=1;
      }
      int n1 = rep[i][1];
      int n2 = rep[i][comp[i]];
      b[n1][n2]=1;
      b[n2][n1]=1;
    }
  }
  
  if(chk==0){return 0;}
  
  build(b);
  return 1;
}

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