제출 #1200359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1200359		pera	Connecting Supertrees (IOI20_supertrees)	C++20	21 / 100	176 ms	22272 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);
   for(int i = 0;i < n;i ++){
      int c1 = 0 , c2 = 0;
      for(int j = 0;j < n;j ++){
         c1 += (p[i][j] == 1);
         c2 += (p[i][j] == 2);
      }
      if(c1 == 1 && c2 == d.sz[d.find(i)] - 1 && c2 > 0){
         cyc[d.find(i)].emplace_back(i);
      }
   } 
   for(int i = 0;i < n;i ++){
      if(d.find(i) == i){
         int c = (int)cyc[i].size() + (int)v[i].size();
         if(c != d.sz[i]){
            return 0;
         }
         if((int)v[i].size() > 0){
            cyc[i].emplace_back(v[i][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 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;
         }
      }
   }
   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