Submission #1238023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238023		SalihSahin	Connecting Supertrees (IOI20_supertrees)	C++20	21 / 100	151 ms	22116 KiB

supertrees

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

vector<int> par;

int fnd(int a){
   if(a == par[a]) return a;
   return par[a] = fnd(par[a]);
}

void merge(int a, int b){
   a = fnd(a);
   b = fnd(b);
   par[b] = a;
}

int construct(vector<vector<int>> p) {
   int n = p.size();
   par.resize(n);
   for(int i = 0; i < n; i++){
      par[i] = i;
   }

   for(int i = 0; i < n; i++){
      for(int j = i+1; j < n; j++){
         if(p[i][j] > 0) merge(i, j);
      }
   }

   bool pos = 1;
   for(int i = 0; i < n; i++){
      for(int j = i+1; j < n; j++){
         if(p[i][j] == 0 && fnd(i) == fnd(j)){
            pos = 0;
         }
      }
   }

   if(!pos){
      return 0;
   }

   vector<vector<int> > ans(n, vector<int>(n, 0));
   vector<int> lst(n, -1);
   for(int i = 0; i < n; i++){
      int g = fnd(i);
      if(lst[g] != -1){
         ans[lst[g]][i] = ans[i][lst[g]] = 1;
      }
      lst[g] = i;
   }

   build(ans);
   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