Submission #658786

#	Time	Username	Problem	Language	Result	Execution time	Memory
658786		evenvalue	Connecting Supertrees (IOI20_supertrees)	C++17	96 / 100	187 ms	27912 KiB

supertrees

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

template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using max_heap = priority_queue<T, vector<T>, less<T>>;

using int64 = long long;
using ld = long double;

constexpr int kInf = 1e9 + 10;
constexpr int64 kInf64 = 1e15 + 10;
constexpr int kMod = 1e9 + 7;

class dsu {
  int n;
  std::vector<int> e;

  int pfind(const int x) {
    return (e[x] < 0 ? x : pfind(e[x]));
  }

public:
  dsu() : n(0), comp(0) {}
  explicit dsu(const int n) : n(n), comp(n), e(n, -1) {}

  int comp;

  int find(const int x) {
    assert(0 <= x and x < n);
    return pfind(x);
  }

  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (e[x] > e[y]) swap(x, y);
    e[x] += e[y];
    e[y] = x;
    comp--;
    return true;
  }

  bool same(const int x, const int y) {
    return (find(x) == find(y));
  }

  int size(const int x) {
    return -e[find(x)];
  }

  std::vector<std::vector<int>> components() {
    std::vector<std::vector<int>> res(n);
    for (int x = 0; x < n; x++) {
      res[pfind(x)].push_back(x);
    }
    res.erase(
        std::remove_if(res.begin(), res.end(), [&](const std::vector<int> &v) { return v.empty(); }),
        res.end());
    return res;
  }
};

vector<vector<int>> ways;
vector<vector<int>> ans;

void connect(const int x, const int y) {
  ans[x][y] = 1;
  ans[y][x] = 1;
}

bool connect1(const vector<int> &nodes) {
  if (nodes.size() < 2) return false;
  for (int i = 0; i < nodes.size() - 1; i++) {
    connect(nodes[i], nodes[i + 1]);
  }
  return true;
}

bool connect2(const vector<int> &nodes) {
  if (nodes.size() < 3) return false;
  connect1(nodes);
  connect(nodes.front(), nodes.back());
  return true;
}

bool connect3(const vector<int> &nodes) {
  if (nodes.size() < 4) return false;
  connect2(nodes);
  connect(nodes[0], nodes[2]);
  return true;
}

bool solve(const vector<int> &nodes) {
  const int n = (int) nodes.size();

  bool two = false;
  bool three = false;

  dsu d(n);
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      const int way = ways[nodes[i]][nodes[j]];
      if (way == 1) {
        d.unite(i, j);
      } else if (way == 2) {
        two = true;
      } else {
        three = true;
      }
    }
  }

  if (two and three) return false;

  const vector<vector<int>> lines = d.components();
  for (auto line : lines) {
    for (int i = 0; i < line.size(); i++) {
      for (int j = i + 1; j < line.size(); j++) {
        const int x = nodes[line[i]];
        const int y = nodes[line[j]];
        if (ways[x][y] != 1) return false;
      }
    }
    for (int &x : line) {
      x = nodes[x];
    }
    connect1(line);
  }

  if (lines.size() == 1) {
    assert(not two);
    assert(not three);
    return true;
  }

  assert(two xor three);

  vector<int> cycle;
  for (const auto &line : lines) {
    cycle.push_back(nodes[line[0]]);
  }

  return (two ? connect2(cycle) : connect3(cycle));
}

int construct(vector<std::vector<int>> p) {
  const int n = (int) p.size();
  ways = p;

  dsu d(n);
  vector<pair<int, int>> disjoint;
  for (int x = 0; x < n; x++) {
    for (int y = x + 1; y < n; y++) {
      if (p[x][y] == 0) {
        disjoint.emplace_back(x, y);
      } else {
        d.unite(x, y);
      }
    }
  }

  for (const auto &[x, y] : disjoint) {
    if (d.same(x, y)) return false;
  }

  ans.assign(n, vector<int>(n));

  const auto components = d.components();
  for (const auto &component : components) {
    if (not solve(component)) return false;
  }

  build(ans);
  return true;
}

Compilation message (stderr)

supertrees.cpp: In constructor 'dsu::dsu(int)':
supertrees.cpp:29:7: warning: 'dsu::comp' will be initialized after [-Wreorder]
   29 |   int comp;
      |       ^~~~
supertrees.cpp:19:20: warning:   'std::vector<int> dsu::e' [-Wreorder]
   19 |   std::vector<int> e;
      |                    ^
supertrees.cpp:27:12: warning:   when initialized here [-Wreorder]
   27 |   explicit dsu(const int n) : n(n), comp(n), e(n, -1) {}
      |            ^~~
supertrees.cpp: In function 'bool connect1(const std::vector<int>&)':
supertrees.cpp:76:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for (int i = 0; i < nodes.size() - 1; i++) {
      |                   ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp: In function 'bool solve(const std::vector<int>&)':
supertrees.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (int i = 0; i < line.size(); i++) {
      |                     ~~^~~~~~~~~~~~~
supertrees.cpp:121:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |       for (int j = i + 1; j < line.size(); j++) {
      |                           ~~^~~~~~~~~~~~~

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