Submission #1264672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264672		uzukishinobu	Connecting Supertrees (IOI20_supertrees)	C++20	96 / 100	219 ms	74012 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
int a;
vector <vector<int>> ans,z;

struct dsu{
      int par[1000005];
      set<int> sz[10005];
      int tplt=0;
      void init(){
          tplt=0;
          for (int i=0;i<=a;i++){
             par[i]=i;
             sz[i].clear();
             sz[i].insert(i);
          }
      }
      int find(int u){
          if (par[u]==u){
              return u;
          }
          return par[u]=find(par[u]);
      }
      bool join(int x,int y){
          x=find(x);
          y=find(y);
          if (x==y){
              return false;
          }
          if (sz[x]<sz[y]){
              swap(x,y);
          }
          for (auto p:sz[y]){
              sz[x].insert(p);
          }
          par[y]=x;
          tplt--;
          return true;
      }
      void off(){
          tplt=0;
      }
      void on(int n){
          par[n]=n;
          sz[n].clear();
          sz[n].insert(n);
          tplt++;
      }
};
dsu d,d1;
vector <int> v;
bool check=true;
void query(){
    set<int> s;
    d1.off();
    for (int i=0;i<v.size();i++){
//         cout << v[i] << " ";
         d1.on(v[i]);
         for (int j=i;j<v.size();j++){
              s.insert(z[v[i]][v[j]]);
         }
    }
    if (s.size()==0){
        return;
    }
//    cout << "\n";
    if (s.size()>2){
        check=false;
        return;
    }
//    cout << "ok" << "\n";
    int p=*s.rbegin();
    for (int i=0;i<v.size();i++){
         for (int j=i+1;j<v.size();j++){
              if (z[v[i]][v[j]]==1){
                 if (d1.join(v[i],v[j])){
                     ans[v[i]][v[j]]=ans[v[j]][v[i]]=1;
                 }
              }
         }
    }
//    cout << d1.tplt << " " << p << "\n";
    if (s.size()==1){
        return;
    }
//    cout << d1.tplt << "\n";
    if (d1.tplt<=p){
        check=false;
        return;
    }
//    cout << "ok" << "\n";
    vector <int> v1;
    for (int i=0;i<v.size();i++){
         if (d1.find(v[i])==v[i]){
             v1.push_back(v[i]);
         }
    }
    for (int i=0;i+1<v1.size();i++){
         ans[v1[i]][v1[i+1]]=ans[v1[i+1]][v1[i]]=1;
         d1.join(v1[i],v1[i+1]);
    }
    ans[v1[0]][v1[v1.size()-1]]=ans[v1[v1.size()-1]][v1[0]]=1;
    if (p==3){
        ans[v1[1]][v1[v1.size()-1]]=ans[v1[v1.size()-1]][v1[1]]=1;
    }
//    cout << "ok" << "\n";
}

int construct(vector<vector<int>> p) {
    a = p.size();
    ans.resize(a,vector<int>(a));
    z=p;
	d.init();
	for (int i=0;i<a;i++){
         for (int j=0;j<a;j++){
              if (p[i][j]>0){
                  d.join(i,j);
              }
         }
	}
//	cerr << "ok" << "\n";
	for (int i=0;i<a;i++){
         if (i==d.find(i)){
             for (auto p:d.sz[i]){
                  v.push_back(p);
             }
             query();
             v.clear();
             if (check==false){
                 return 0;   
                 break;
             }
         }
//         cerr << i << "\n";
	}
	if (check){
        build(ans);
        return 1;
	}else{
	}
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:142:1: warning: control reaches end of non-void function [-Wreturn-type]
  142 | }
      | ^

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