Submission #937791

#	Time	Username	Problem	Language	Result	Execution time	Memory
937791		Hugo1729	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1 ms	600 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)groups.connect(i,j);
      }
    }
    vector<int> row;
    row.assign(n,0);
    answer.push_back(row);
  }

  for (int i = 0; i < n; i++){
    for(int j=0;j<n;j++){
      if(j!=i){
        if(p[i][j]==0&&groups.same(i,j))return 0;
      }
    }
  }

  for (int i = 0; i < n; i++){
    for(int j=0;j<n;j++){
      if(j!=i){
        if(p[i][j]==1&&!rep.same(i,j)){
          rep.connect(i,j);
          for(int k=0;k<n;k++){
            if(p[i][k]!=p[j][k])return 0;
          }
        }
      }
    }
  }

  for (int i = 0; i < n; i++){
    for(int j=0;j<n;j++){
      if(j!=i){
        if(groups.same(i,j)){
          if(p[i][j]==0)return 0;
          else if(p[i][j]==1){
            if(!rep.same(i,j))return 0;
          } else if(p[i][j]==2){
            if(rep.same(i,j))return 0;
          } else if(p[i][j]==3)return 0;
        }else{
          if(p[i][j]>0)return 0;
        }
      }
    }
  }
  vector<vector<int>> circles;
  int t=0;
  map<int,int> mcircles;
  for(int i=0;i<n;i++){
    if(rep.find(i)==i){
      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{
      answer[i][rep.find(i)]=1;
      answer[rep.find(i)][i]=1;
    }
  }

  // cout << "dsfasdfsdafsda";

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

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