Submission #1318649

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318649		ElayV13	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	120 ms	30240 KiB

supertrees

#include "supertrees.h"
#include "bits/stdc++.h"
using namespace std;
const int N = 1001;

int n , comp[N] , par[N];
vector < vector < int > > res;
vector < int > G[N] , C[N] , F[N];
bool vis[N];
int cur_comp = 0;

void add_edge(int ii , int jj , bool g){
   if(!g){
      res[ii][jj] = 1;
      res[jj][ii] = 1;
   }
   else{
      G[ii].push_back(jj);
      G[jj].push_back(ii);
   }
}
void dfs(int v){
   comp[v] = cur_comp;
   C[cur_comp].push_back(v);
   vis[v] = 1;
   for(int u : G[v]){
      if(!vis[u]) dfs(u);
   }
}
bool used[N];
vector < int > nodes;
vector < vector < int > > all;
void DFS(int v){
   nodes.push_back(v);
   used[v] = 1;
   for(int u : F[v])
   {
      if(!used[u]) DFS(u);
   }
}
bool ok(vector < vector < int > > p){
   for(int i = 0;i < n;i++){
         for(int j = 0;j < n;j++){
            if(p[i][j] == 2 && par[i] == par[j] && par[i] != -1 && par[j] != -1) return false;
            if(p[i][j] > 0 && (comp[i] != comp[j])) return false;
            if(p[i][j] == 0 && (comp[i] == comp[j])) return false;
            if(p[i][j] == 2)
            {
               if(C[comp[i]].size() == 2) return false;
            }
         }
   }
   return true;
}
int construct(vector < vector < int > > p)
{
   n = p.size();
   for(int i = 0;i < n;i++) par[i] = -1;
   res.assign(n , vector < int > (n));
   for(int i = 0;i < n - 1;i++){
      for(int j = i + 1;j < n;j++){
         if(p[i][j] > 0){
            add_edge(i , j , 1);
            if(p[i][j] == 1){
               F[i].push_back(j);
               F[j].push_back(i);
            }
         }
      }
   }
   for(int i = 0;i < n;i++)
   {
      if(!vis[i]) ++cur_comp , dfs(i);
   }
   for(int i = 1;i <= cur_comp;i++)
   {
      bool cont3 = 0;
      for(int node1 : C[i]) for(int node2 : C[i]) cont3 |= (p[node1][node2] == 3);
      if(!cont3){
         all.clear();
         for(int node : C[i])
         {
            if(!used[node])
            {
               nodes.clear();
               DFS(node);
               all.push_back(nodes);
            }
         }
         if(all.size() == 1){
            for(int j = 0;j < all[0].size() - 1;j++) add_edge(all[0][j] , all[0][j + 1] , 0);
            continue;
         }
         else{
            for(int j = 0;j < all.size();j++){
               for(int ii = 0;ii < all[j].size() - 1;ii++) add_edge(all[j][ii] , all[j][ii + 1] , 0);
            }
            for(int j = 0;j < all.size();j++){
               for(int ii = 0;ii < all[j].size();ii++) par[all[j][ii]] = all[j][0];
            }
            for(int j = 0;j < all.size() - 1;j++) add_edge(all[j][0] , all[j + 1][0] , 0);
            add_edge(all[0][0] , all[all.size() - 1][0] , 0);
         }
      }
      else{
         all.clear();
         for(int node : C[i])
         {
            if(!used[node])
            {
               nodes.clear();
               DFS(node);
               if(nodes.size() > 1) all.push_back(nodes);
            }
         }
         if(all.size() != 1) return 0;
         for(int j = 0;j < all[0].size() - 1;j++) add_edge(all[0][j] , all[0][j + 1] , 0);
         vector < bool > usd(n , false);
         for(int node : all[0]) usd[node] = 1;
         vector < int > f1 , f2;
         for(int node : C[i]){
            if(!usd[node]){
               for(int j = 0;j < n;j++){
                  if(usd[j]) continue;
                  if(p[node][j] == 2 or node == j) f1.push_back(j);
                  else if(p[node][j] == 3) f2.push_back(j);
               }
               break;
            }
         }
         if(f1.size() <= 1) return 0;
         if(f2.size() <= 1) return 0;
         for(int j = 0;j < f1.size() - 1;j++) add_edge(f1[j] , f1[j + 1] , 0);
         for(int j = 0;j < f2.size() - 1;j++) add_edge(f2[j] , f2[j + 1] , 0);
         add_edge(all[0][0] , f1[0] , 0);
         add_edge(all[0][0] , f1[f1.size() - 1] , 0);
         add_edge(all[0][all[0].size() - 1] , f2[0], 0);
         add_edge(all[0][all[0].size() - 1] , f2[f2.size() - 1] , 0);
      }
   }
   if(!ok(p)) return 0;
   build(res);
   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