Submission #1221962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221962		hmms127	Connecting Supertrees (IOI20_supertrees)	C++20	21 / 100	133 ms	22212 KiB

supertrees

#include "supertrees.h"
#include <vector>
using namespace std;
struct DSU{
  vector<int>par,sz;
  void init(int n){
      par.resize(n+1);sz.resize(n+1);
      for(int i=0;i<n;i++)par[i]=i,sz[i]=1;
  }  
  int root(int u){
      return par[u]==u ? u:par[u]=root(par[u]);
  }
  bool merge(int u,int v){
      int ru=root(u),rv=root(v);
      if(ru==rv)return 0;
      if(sz[ru]>sz[rv])swap(sz[ru],sz[rv]);
      par[ru]=rv;sz[rv]+=sz[ru];
      return 1;
  }
};

int construct(std::vector<std::vector<int>> p) {
	int n=p[0].size();
    vector<vector<int>>v(n,vector<int>(n,0));
    DSU d1;d1.init(n);
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(p[i][j]==0)continue;
            d1.merge(i,j);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(p[i][j]==0&&d1.root(i)==d1.root(j))return 0;
        }
    }
    vector<vector<int>>comp(n);
    for(int i=0;i<n;i++){
        comp[d1.root(i)].push_back(i);
    }
    for(int i=0;i<n;i++){
        if(comp[i].size()){
           bool valid=0;
           for(int j=0;j<comp[i].size();j++){
               for(int k=0;k<comp[i].size();k++){
                   if(p[comp[i][j]][comp[i][k]]==2){valid=1;break;}
               }
               if(valid)break;
           }
           if(valid){
               if(comp[i].size()<3)return 0;
               for(int j=0;j<comp[i].size();j++){
                   int u=comp[i][j],v1=comp[i][(j+1)%(comp[i].size())];
                   v[u][v1]=1;v[v1][u]=1;
               }
               for(int j=0;j<comp[i].size();j++){
               for(int k=0;k<comp[i].size();k++){
                   if(p[comp[i][j]][comp[i][k]]!=2){return 0;}
               }
           }
               
           }
           else {
              for(int j=1;j<comp[i].size();j++){
                   int u=comp[i][j],v1=comp[i][j-1];
                   v[u][v1]=1;v[v1][u]=1;
               } 
           }
        }
    }
	build(v);
	return 1;
}

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