Submission #937747

#	Time	Username	Problem	Language	Result	Execution time	Memory
937747		Hugo1729	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	182 ms	24224 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

struct DSU{
int n;
vector<int> e;

DSU(int s){
  n=s;e.assign(n,-1);
}
int find(int v){
  return (e[v]<0?v:e[v]=find(e[v]));
}
bool same(int a, int b){
  return find(a)==find(b);
}
bool connect(int a, int b){
  a=find(a);b=find(b);
  if(a==b)return 0;
  if(e[a]>e[b])swap(a,b);
  e[a]+=e[b];
  e[b]=a;
  return 1;
}
};

int construct(vector<vector<int>> p) {
  int n = p.size();
  DSU groups(n),rep(n);
  vector<vector<int>> answer;
  for (int i = 0; i < n; i++){
    for(int j=0;j<n;j++){
      if(j!=i){
        if(p[i][j]==0){
          if(groups.same(i,j))return 0;
        }else if(p[i][j]==1){
          if(!rep.same(i,j)){
            bool flag=1;
            for(int k=0;k<n;k++){
              if(p[i][k]!=p[j][k]){
                flag=0;
              }
            }
            if(flag){
              rep.connect(i,j);
              groups.connect(i,j);
            } else{
              return 0;
            }
          }
        } else if(p[i][j]==2){
          if(rep.same(i,j))return 0;
          groups.connect(i,j);
        }
      }
    }
    vector<int> row;
    row.assign(n,0);
    answer.push_back(row);
  }

  vector<vector<int>> circles;
  int t=0;
  map<int,int> mcircles;
  for(int i=0;i<n;i++){
    if(rep.e[i]<0){
      if(mcircles.count(groups.find(i))==0){
        circles.push_back({rep.find(i)});
        mcircles[groups.find(i)]=t;
        t++;
      } else{
        circles[mcircles[groups.find(i)]].push_back(rep.find(i));
      }
    }else{
      if(rep.find(i)!=i){
        answer[i][rep.find(i)]=1;
        answer[rep.find(i)][i]=1;
      }
    }
  }

  // cout << "dsfasdfsdafsda";

  for(vector<int> h : circles){
    for(int j=0;j<h.size();j++){
      if(h.size()<=1)continue;
      answer[h[j]][h[(j+1)%h.size()]]=1;
      answer[h[(j+1)%h.size()]][h[j]]=1;
      cout << h[j] << '\n';
    }
  }
  
  build(answer);
  return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int j=0;j<h.size();j++){
      |                 ~^~~~~~~~~

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