Submission #1238077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238077		SalihSahin	Connecting Supertrees (IOI20_supertrees)	C++20	96 / 100	128 ms	22248 KiB

supertrees

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

vector<int> par, par2;
vector<vector<int> > group;

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

void merge(int a, int b){
   a = fnd(a);
   b = fnd(b);
   if(a == b) return;

   if(group[a].size() > group[b].size()){
      par[b] = a;
      for(auto itr: group[b]){
         group[a].pb(itr);
      }
      group[b].clear();
   }
   else{
      swap(a, b);
      par[b] = a;
      for(auto itr: group[b]){
         group[a].pb(itr);
      }
      group[b].clear();
   }
}

int fnd2(int a){
   if(a == par2[a]) return a;
   else return par2[a] = fnd2(par2[a]);
}

void merge2(int a, int b){
   a = fnd2(a);
   b = fnd2(b);
   if(a == b) return;
   par2[b] = a;
}

int construct(vector<vector<int>> p) {
   int n = p.size();
   par.resize(n);
   group.resize(n);
   for(int i = 0; i < n; i++){
      par[i] = i;
      group[i].pb(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> cand(n, -1);

   par2.resize(n);
   for(int i = 0; i < n; i++){
      par2[i] = i;
   }

   bool pos2 = 1;

   for(int i = 0; i < n; i++){
      if(par[i] != i) continue;

      for(int j = 0; j < group[i].size(); j++){
         for(int k = j+1; k < group[i].size(); k++){
            int aj = group[i][j], ak = group[i][k];
            if(p[aj][ak] == 1){
               merge2(aj, ak);
            }
         }
      }

      for(int j = 0; j < group[i].size(); j++){
         for(int k = j+1; k < group[i].size(); k++){
            int aj = group[i][j], ak = group[i][k];
            if(p[aj][ak] == 2 && fnd2(aj) == fnd2(ak)){
               pos2 = 0;
            }
         }
      }

      vector<int> gstart;

      for(int j = 0; j < group[i].size(); j++){
         int aj = group[i][j];
         int gaj = fnd2(aj);
         if(cand[gaj] == -1){
            cand[gaj] = aj;
            gstart.pb(aj);
         }
         else{
            ans[cand[gaj]][aj] = ans[aj][cand[gaj]] = 1;
            cand[gaj] = aj;
         }
      }

      if(gstart.size() == 2){ // 2 pair arası birden fazla edge var
         pos2 = 0; 
      }

      for(int j = 1; j < gstart.size(); j++){
         ans[gstart[j]][gstart[j-1]] = ans[gstart[j-1]][gstart[j]] = 1;
      }
      if(gstart.size() > 1){
         ans[gstart[0]][gstart[gstart.size()-1]] = ans[gstart[gstart.size()-1]][gstart[0]] = 1;
      }
   }

   if(!pos2){
      return 0;
   }

   build(ans);
   return 1;
}

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