kyopro-lib

This documentation is automatically generated by online-judge-tools/verification-helper

View on GitHub

:heavy_check_mark: test/aoj/2559/main.binomial_heap.test.cpp

Depends on

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2559"

#include <iostream>
#include <map>
#include <set>
#include <tuple>
#include <vector>
#include "Mylib/DataStructure/Heap/binomial_heap.cpp"
#include "Mylib/Graph/MinimumSpanningTree/prim.cpp"
#include "Mylib/Graph/Template/graph.cpp"
#include "Mylib/Misc/merge_technique.cpp"
#include "Mylib/Utils/fix_point.cpp"

namespace hl = haar_lib;

int main() {
  int n, m;
  std::cin >> n >> m;

  hl::graph<int64_t> g(n);
  g.read<1, false>(m);

  std::map<std::pair<int, int>, int> index;
  for (auto &a : g) {
    for (auto &e : a) index[{e.from, e.to}] = e.index;
  }

  auto res = hl::prim(g);

  std::vector<int64_t> ans(m, -1);

  if ((int) res.size() == n - 1) {
    int64_t s = 0;
    hl::tree<int64_t> tree(n);

    for (auto &e : res) {
      s += e.cost;
      tree[e.from].push_back(e);
    }

    ans.assign(m, s);

    std::vector<hl::binomial_heap<std::tuple<int64_t, int, int>, std::greater<>>> heaps(n);

    std::vector<std::set<int>> sub(n);

    hl::make_fix_point(
        [&](auto &&f, int cur, int par, int64_t cost) -> void {
          for (auto &e : g[cur]) {
            heaps[cur].push({e.cost, e.from, e.to});
          }

          sub[cur].insert(cur);

          for (auto &e : tree[cur]) {
            if (e.to == par) continue;
            f(e.to, cur, e.cost);

            heaps[cur].meld(heaps[e.to]);
            hl::merge_technique(sub[cur], sub[cur], sub[e.to]);
          }

          if (par != -1) {
            while (not heaps[cur].empty()) {
              auto [c, i, j] = heaps[cur].top();
              if ((sub[cur].find(i) != sub[cur].end() and sub[cur].find(j) != sub[cur].end()) or
                  (i == cur and j == par) or (i == par and j == cur)) {
                heaps[cur].pop();
              } else {
                break;
              }
            }

            if (not heaps[cur].empty()) {
              ans[index[{cur, par}]] = s - cost + std::get<0>(heaps[cur].top());
            } else {
              ans[index[{cur, par}]] = -1;
            }
          }
        })(0, -1, 0);
  }

  for (auto x : ans) {
    std::cout << x << std::endl;
  }

  return 0;
}
#line 1 "test/aoj/2559/main.binomial_heap.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2559"

#include <iostream>
#include <map>
#include <set>
#include <tuple>
#include <vector>
#line 2 "Mylib/DataStructure/Heap/binomial_heap.cpp"
#include <array>
#include <cassert>
#include <functional>
#line 6 "Mylib/DataStructure/Heap/binomial_heap.cpp"

namespace haar_lib {
  template <typename T, typename Compare = std::less<T>>
  class binomial_heap {
  public:
    using value_type = T;

  private:
    struct node {
      T value;
      std::vector<node *> children;
      node(T value) : value(value) {}
    };

    constexpr static int MAX = 31;

    std::array<node *, MAX> roots_;
    Compare compare_;
    int top_index_ = -1;
    int heap_size_ = 0;

    node *merge(node *a, node *b) {
      if (compare_(a->value, b->value)) std::swap(a, b);
      a->children.push_back(b);
      return a;
    }

    template <typename Container>
    void meld(Container c) {
      node *s = nullptr;

      for (int i = 0; i < MAX; ++i) {
        std::vector<node *> temp;
        if (s) {
          temp.push_back(s);
          s = nullptr;
        }
        if (roots_[i]) {
          temp.push_back(roots_[i]);
          roots_[i] = nullptr;
        }
        if (i < (int) c.size() and c[i]) {
          temp.push_back(c[i]);
          c[i] = nullptr;
        }

        switch (temp.size()) {
          case 1: roots_[i] = temp[0]; break;
          case 2: s = merge(temp[0], temp[1]); break;
          case 3:
            roots_[i] = temp[0];
            s         = merge(temp[1], temp[2]);
            break;
        }
      }

      top_index_ = -1;
      for (int i = 0; i < MAX; ++i) {
        if (roots_[i]) {
          if (top_index_ == -1 or compare_(roots_[top_index_]->value, roots_[i]->value)) {
            top_index_ = i;
          }
        }
      }
    }

  public:
    binomial_heap() {
      roots_.fill(nullptr);
      compare_ = Compare();
    }

    int size() const {
      return heap_size_;
    }

    bool empty() const {
      return heap_size_ == 0;
    }

    void push(const T &value) {
      heap_size_ += 1;
      node *t = new node(value);

      meld(std::vector<node *>({t}));
    }

    const T &top() const {
      return roots_[top_index_]->value;
    }

    void pop() {
      heap_size_ -= 1;

      node *t            = roots_[top_index_];
      roots_[top_index_] = nullptr;
      meld(t->children);

      delete t;
    }

    void meld(binomial_heap &rhs) {
      heap_size_ += rhs.heap_size_;
      meld(rhs.roots_);
      rhs.roots_.fill(nullptr);
    }
  };
}  // namespace haar_lib
#line 2 "Mylib/Graph/MinimumSpanningTree/prim.cpp"
#include <queue>
#line 4 "Mylib/Graph/Template/graph.cpp"

namespace haar_lib {
  template <typename T>
  struct edge {
    int from, to;
    T cost;
    int index = -1;
    edge() {}
    edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
    edge(int from, int to, T cost, int index) : from(from), to(to), cost(cost), index(index) {}
  };

  template <typename T>
  struct graph {
    using weight_type = T;
    using edge_type   = edge<T>;

    std::vector<std::vector<edge<T>>> data;

    auto& operator[](size_t i) { return data[i]; }
    const auto& operator[](size_t i) const { return data[i]; }

    auto begin() const { return data.begin(); }
    auto end() const { return data.end(); }

    graph() {}
    graph(int N) : data(N) {}

    bool empty() const { return data.empty(); }
    int size() const { return data.size(); }

    void add_edge(int i, int j, T w, int index = -1) {
      data[i].emplace_back(i, j, w, index);
    }

    void add_undirected(int i, int j, T w, int index = -1) {
      add_edge(i, j, w, index);
      add_edge(j, i, w, index);
    }

    template <size_t I, bool DIRECTED = true, bool WEIGHTED = true>
    void read(int M) {
      for (int i = 0; i < M; ++i) {
        int u, v;
        std::cin >> u >> v;
        u -= I;
        v -= I;
        T w = 1;
        if (WEIGHTED) std::cin >> w;
        if (DIRECTED)
          add_edge(u, v, w, i);
        else
          add_undirected(u, v, w, i);
      }
    }
  };

  template <typename T>
  using tree = graph<T>;
}  // namespace haar_lib
#line 5 "Mylib/Graph/MinimumSpanningTree/prim.cpp"

namespace haar_lib {
  template <typename T>
  std::vector<edge<T>> prim(const graph<T> &graph) {
    const int n = graph.size();
    std::vector<bool> visit(n, false);
    std::vector<edge<T>> ret;

    auto cmp = [](const auto &a, const auto &b) { return a.cost > b.cost; };
    std::priority_queue<edge<T>, std::vector<edge<T>>, decltype(cmp)> pq(cmp);

    visit[0] = true;
    for (auto &e : graph[0]) pq.push(e);

    while (not pq.empty()) {
      auto t = pq.top();
      pq.pop();

      if (visit[t.from] == visit[t.to]) continue;

      int i = visit[t.from] ? t.to : t.from;
      for (auto &e : graph[i]) {
        pq.push(e);
      }

      visit[i] = true;
      ret.push_back(t);
    }

    return ret;
  }
}  // namespace haar_lib
#line 3 "Mylib/Misc/merge_technique.cpp"
#include <utility>

namespace haar_lib {
  template <typename T>
  void merge_technique(std::set<T> &res, std::set<T> &a, std::set<T> &b) {
    if (a.size() > b.size()) {
      a.insert(b.begin(), b.end());
      std::swap(res, a);
    } else {
      b.insert(a.begin(), a.end());
      std::swap(res, b);
    }
  }
}  // namespace haar_lib
#line 3 "Mylib/Utils/fix_point.cpp"

namespace haar_lib {
  template <typename F>
  struct fix_point : F {
    explicit constexpr fix_point(F &&f) noexcept : F(std::forward<F>(f)) {}

    template <typename... Args>
    constexpr auto operator()(Args &&... args) const {
      return F::operator()(*this, std::forward<Args>(args)...);
    }
  };

  template <typename F>
  inline constexpr auto make_fix_point(F &&f) {
    return fix_point<F>(std::forward<F>(f));
  }

  template <typename F>
  inline constexpr auto make_fix_point(F &f) {
    return fix_point<F>(std::forward<F>(f));
  }
}  // namespace haar_lib
#line 13 "test/aoj/2559/main.binomial_heap.test.cpp"

namespace hl = haar_lib;

int main() {
  int n, m;
  std::cin >> n >> m;

  hl::graph<int64_t> g(n);
  g.read<1, false>(m);

  std::map<std::pair<int, int>, int> index;
  for (auto &a : g) {
    for (auto &e : a) index[{e.from, e.to}] = e.index;
  }

  auto res = hl::prim(g);

  std::vector<int64_t> ans(m, -1);

  if ((int) res.size() == n - 1) {
    int64_t s = 0;
    hl::tree<int64_t> tree(n);

    for (auto &e : res) {
      s += e.cost;
      tree[e.from].push_back(e);
    }

    ans.assign(m, s);

    std::vector<hl::binomial_heap<std::tuple<int64_t, int, int>, std::greater<>>> heaps(n);

    std::vector<std::set<int>> sub(n);

    hl::make_fix_point(
        [&](auto &&f, int cur, int par, int64_t cost) -> void {
          for (auto &e : g[cur]) {
            heaps[cur].push({e.cost, e.from, e.to});
          }

          sub[cur].insert(cur);

          for (auto &e : tree[cur]) {
            if (e.to == par) continue;
            f(e.to, cur, e.cost);

            heaps[cur].meld(heaps[e.to]);
            hl::merge_technique(sub[cur], sub[cur], sub[e.to]);
          }

          if (par != -1) {
            while (not heaps[cur].empty()) {
              auto [c, i, j] = heaps[cur].top();
              if ((sub[cur].find(i) != sub[cur].end() and sub[cur].find(j) != sub[cur].end()) or
                  (i == cur and j == par) or (i == par and j == cur)) {
                heaps[cur].pop();
              } else {
                break;
              }
            }

            if (not heaps[cur].empty()) {
              ans[index[{cur, par}]] = s - cost + std::get<0>(heaps[cur].top());
            } else {
              ans[index[{cur, par}]] = -1;
            }
          }
        })(0, -1, 0);
  }

  for (auto x : ans) {
    std::cout << x << std::endl;
  }

  return 0;
}
Back to top page