Submission #1200419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200419		pera	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	172 ms	22364 KiB

supertrees

#include "supertrees.h"
#include "bits/stdc++.h"
#include <vector>
using namespace std;
struct dsu{
   int n , cnt;
   vector<int> P , sz;
   dsu(int _size){
      n = _size;
      cnt = _size;
      P = vector<int>(_size + 1);
      iota(P.begin() , P.end() , 0);
      sz = vector<int>(_size + 1);
      fill(sz.begin() , sz.end() , 1);
   }  
   function<int(int)> find = [&](int u){
      return u == P[u] ? u : P[u] = find(P[u]);
   };
   function<bool(int , int)> same = [&](int u , int v){
      return find(u) == find(v);
   };
   function<bool(int , int)> join = [&](int u , int v){
      u = find(u);
      v = find(v);
      if(u != v){
         if(sz[u] < sz[v]){
            swap(u , v);
         }
         P[v] = u;
         sz[u] += sz[v];
         --cnt;
         return true;
      }
      return false;
   };
};
int construct(std::vector<std::vector<int>> p) {
	int n = (int)p.size();
   dsu d(n);
   for(int i = 0;i < n;i ++){
      for(int j = 0;j < n;j ++){
         if(p[i][j] > 0){
            d.join(i , j);
         }
      }
   }
   for(int i = 0;i < n;i ++){
      for(int j = 0;j < n;j ++){
         if(d.same(i , j) && !p[i][j]){
            return 0;
         }
      }
   }
   dsu dx(n);
   for(int i = 0;i < n;i ++){
      for(int j = 0;j < n;j ++){
         if(p[i][j] == 1){
            dx.join(i , j);
         }
      }
   }
   for(int i = 0;i < n;i ++){
      for(int j = 0;j < n;j ++){
         if(dx.same(i , j) && p[i][j] != 1){
            return 0;
         }
      }
   }
   vector<vector<int>> ans(n , vector<int>(n));
   vector<vector<int>> v(n);
   for(int i = 0;i < n;i ++){
      v[dx.find(i)].emplace_back(i);
   }
   for(int i = 0;i < n;i ++){
      for(int j = 0;j + 1 < (int)v[i].size();j ++){
         ans[v[i][j]][v[i][j + 1]] = 1;
         ans[v[i][j + 1]][v[i][j]] = 1;
      }
   }
   vector<int> st(n);
   vector<vector<int>> cyc(n) , w(n);
   for(int i = 0;i < n;i ++){
      w[dx.find(i)].emplace_back(i);
      if(dx.find(i) == i){
         cyc[d.find(i)].emplace_back(i);
      }
   } 
   for(int i = 0;i < n;i ++){
      if(d.find(i) == i){
         if((int)cyc[i].size() == 2){
            return 0;
         }
         if((int)cyc[i].size() > 1){
           for(int j = 0;j < (int)cyc[i].size();j ++){
              int e = (j + 1) % ((int)cyc[i].size());
              ans[cyc[i][j]][cyc[i][e]] = 1;
              ans[cyc[i][e]][cyc[i][j]] = 1;
           }
         }
         for(int x : cyc[i]){
            for(int a : w[x]){
               for(int j = 0;j < n;j ++){
                  if(d.find(j) == i && dx.find(j) != x){
                     if(p[a][j] != 2){
                        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: 4 / 4