Submission #956577

#	Time	Username	Problem	Language	Result	Execution time	Memory
956577		Numberz	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	587 ms	24416 KiB

supertrees

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

int construct(vector<std::vector<int>> p) {
  //subtask 1
  int n = p.size();
  vector<vector<int>> res(n, vector<int>(n, 0));

  //check if even possible
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (p[i][j] == 1) {
        for (int k = j; k < n; k++) {
          if (p[i][j] != 0 && p[i][k] != 0 && p[j][k] == 0) return 0;
        }
      } 
      else if (p[i][j] == 2) {
        for (int k = j; k < n; k++) {
          if (p[i][j] != 0 && p[i][k] != 0 && p[j][k] == 0) return 0;
        }
      }
      else if (p[i][j] == 3) {
        return false;
      }
    }
  }

  //build the components
  //this builds all the needed trees
  vector<vector<int>> trees;
  vector<bool> used(n, false);
  vector<int> roots;

  for (int i = 0; i < n; i++) {
    if (used[i]) continue;
    used[i] = true;
    trees.push_back({i});
    roots.push_back(i);
    for (int j = i+1; j < n; j++) {
      if (p[i][j] == 1) {
        used[j] = true;
        trees[trees.size()-1].push_back(j);
        res[i][j] = 1;
        res[j][i] = 1;
      }
    }
  }

  //we now build cycles out of the roots
  vector<vector<int>> cycles;
  vector<bool> used_cyc(roots.size(), false);
  for (int r = 0; r < roots.size(); r++) {
    if (used_cyc[r]) continue;
    used_cyc[r] = true;
    cycles.push_back({roots[r]});
    for (int j = r+1; j < roots.size(); j++) {
      if (p[roots[r]][roots[j]] == 2) {
        used_cyc[j] = true;
        cycles[cycles.size()-1].push_back(roots[j]);
      }
    }
  }

  for (auto cyc : cycles) {
    if (cyc.size() == 2) {
      return 0;
    }
    if (cyc.size() > 2) {
      int k = cyc.size();
      for (int i = 0; i < k-1; i++) {
        res[cyc[i]][cyc[i+1]] = 1;
        res[cyc[i+1]][cyc[i]] = 1;
      }
      res[cyc[k-1]][cyc[0]] = 1;
      res[cyc[0]][cyc[k-1]] = 1;
    }
  }
  
  build(res);
  return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:53:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for (int r = 0; r < roots.size(); r++) {
      |                   ~~^~~~~~~~~~~~~~
supertrees.cpp:57:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int j = r+1; j < roots.size(); j++) {
      |                       ~~^~~~~~~~~~~~~~

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