#386748 (C++14) No.898 tri-βutree

提出ソース
結果

問題	No.898 tri-βutree
ユーザー	noshi91
提出日時	2019-10-04 22:15:35
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	768 ms / 4,000 ms
コード長	18,243 bytes
コンパイル時間	1,381 ms
コンパイル使用メモリ	99,296 KB
実行使用メモリ	21,760 KB
最終ジャッジ日時	2024-11-08 22:17:44
合計ジャッジ時間	15,301 ms
ジャッジサーバーID （参考情報）	judge1 / judge3
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	339 ms 21,760 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	3 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	3 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	751 ms 19,404 KB
testcase_08	AC	756 ms 19,456 KB
testcase_09	AC	768 ms 19,440 KB
testcase_10	AC	758 ms 19,496 KB
testcase_11	AC	740 ms 19,456 KB
testcase_12	AC	766 ms 19,456 KB
testcase_13	AC	755 ms 19,584 KB
testcase_14	AC	750 ms 19,508 KB
testcase_15	AC	746 ms 19,456 KB
testcase_16	AC	735 ms 19,456 KB
testcase_17	AC	746 ms 19,416 KB
testcase_18	AC	739 ms 19,580 KB
testcase_19	AC	733 ms 19,440 KB
testcase_20	AC	733 ms 19,416 KB
testcase_21	AC	757 ms 19,584 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
//#define NDEBUG
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <vector>

namespace n91 {

  using i8 = std::int_fast8_t;
  using i32 = std::int_fast32_t;
  using i64 = std::int_fast64_t;
  using u8 = std::uint_fast8_t;
  using u32 = std::uint_fast32_t;
  using u64 = std::uint_fast64_t;
  using isize = std::ptrdiff_t;
  using usize = std::size_t;

  constexpr usize operator"" _z(unsigned long long x) noexcept {
    return static_cast<usize>(x);
  }

  template <class T> class integral_iterator {
  public:
    using difference_type = T;
    using value_type = T;
    using pointer = const value_type*;
    using reference = value_type;
    using iterator_category = std::random_access_iterator_tag;

  private:
    using self_type = integral_iterator<value_type>;
    value_type i;

  public:
    constexpr integral_iterator() noexcept : i() {}
    explicit constexpr integral_iterator(const value_type i) noexcept : i(i) {}
    constexpr self_type operator++(int) noexcept { return self_type(i++); }
    constexpr self_type operator--(int) noexcept { return self_type(i--); }
    constexpr self_type operator[](const difference_type rhs) const noexcept {
      return self_type(i + rhs);
    }
    constexpr self_type& operator++() noexcept {
      ++i;
      return *this;
    }
    constexpr self_type& operator--() noexcept {
      --i;
      return *this;
    }
    constexpr reference operator*() const noexcept { return i; }
    constexpr self_type operator+(const difference_type rhs) const noexcept {
      return self_type(i + rhs);
    }
    constexpr self_type operator-(const difference_type rhs) const noexcept {
      return self_type(i - rhs);
    }
    constexpr difference_type operator-(const self_type rhs) const noexcept {
      return i - rhs.i;
    }
    constexpr bool operator<(const self_type rhs) const noexcept {
      return i < rhs.i;
    }
    constexpr bool operator<=(const self_type rhs) const noexcept {
      return i <= rhs.i;
    }
    constexpr bool operator>(const self_type rhs) const noexcept {
      return i > rhs.i;
    }
    constexpr bool operator>=(const self_type rhs) const noexcept {
      return i >= rhs.i;
    }
    constexpr bool operator==(const self_type rhs) const noexcept {
      return i == rhs.i;
    }
    constexpr bool operator!=(const self_type rhs) const noexcept {
      return i != rhs.i;
    }
    constexpr self_type& operator+=(const difference_type rhs) noexcept {
      i += rhs;
      return *this;
    }
    constexpr self_type& operator-=(const difference_type rhs) noexcept {
      i -= rhs;
      return *this;
    }
  };
  template <class T>
  constexpr integral_iterator<T> make_int_itr(const T i) noexcept {
    return integral_iterator<T>(i);
  }
  class rep {
    const usize f, l;

  public:
    constexpr rep(const usize f, const usize l) noexcept : f(f), l(l) {}
    constexpr auto begin() const noexcept { return make_int_itr(f); }
    constexpr auto end() const noexcept { return make_int_itr(l); }
  };
  class revrep {
    const usize f, l;

  public:
    revrep(const usize f, const usize l) noexcept : f(l), l(f) {}
    auto begin() const noexcept {
      return std::make_reverse_iterator(make_int_itr(f));
    }
    auto end() const noexcept {
      return std::make_reverse_iterator(make_int_itr(l));
    }
  };
  template <class T> auto md_vec(const usize n, const T& value) {
    return std::vector<T>(n, value);
  }
  template <class... Args> auto md_vec(const usize n, Args... args) {
    return std::vector<decltype(md_vec(args...))>(n, md_vec(args...));
  }
  template <class T> constexpr T difference(const T& a, const T& b) {
    return a < b ? b - a : a - b;
  }
  template <class T> T scan() {
    T ret;
    std::cin >> ret;
    return ret;
  }

} // namespace n91
#include <cassert>
#include <utility>
#include <vector>

class rooted_trees {
private:
  class node_type;
  using container_type = ::std::vector<node_type>;

public:
  using size_type = typename container_type::size_type;

private:
  class node_type {
    using pointer = node_type *;
    pointer left, right, parent;
    bool reversed;

  public:
    node_type()
      : left(nullptr), right(nullptr), parent(nullptr), reversed(false) {}

    void reverse() { reversed = !reversed; }
    void cut_left() {
      if (left) {
        left->parent = nullptr;
        left = nullptr;
      }
    }
    void push() {
      if (reversed) {
        reversed = false;
        ::std::swap(left, right);
        if (left)
          left->reverse();
        if (right)
          right->reverse();
      }
    }
    void set_left_of(const pointer ptr) {
      ptr->left = this;
      parent = ptr;
    }
    void set_right_of(const pointer ptr) {
      ptr->right = this;
      parent = ptr;
    }
    void rotate_as_left(const pointer ptr) {
      if (right)
        right->set_left_of(ptr);
      else
        ptr->left = nullptr;
      ptr->set_right_of(this);
    }
    void rotate_as_right(const pointer ptr) {
      if (left)
        left->set_right_of(ptr);
      else
        ptr->right = nullptr;
      ptr->set_left_of(this);
    }
    void splay() {
      for (pointer x, y = this;;) {
        if (x = parent) {
          if (x->left == y) {
            if (y = x->parent) {
              if (y->left == x) {
                parent = y->parent;
                x->rotate_as_left(y);
                rotate_as_left(x);
              }
              else if (y->right == x) {
                parent = y->parent;
                rotate_as_left(x);
                rotate_as_right(y);
              }
              else {
                parent = y;
                rotate_as_left(x);
                return;
              }
            }
            else {
              parent = nullptr;
              rotate_as_left(x);
              return;
            }
          }
          else if (x->right == y) {
            if (y = x->parent) {
              if (y->left == x) {
                parent = y->parent;
                rotate_as_right(x);
                rotate_as_left(y);
              }
              else if (y->right == x) {
                parent = y->parent;
                x->rotate_as_right(y);
                rotate_as_right(x);
              }
              else {
                parent = y;
                rotate_as_right(x);
                return;
              }
            }
            else {
              parent = nullptr;
              rotate_as_right(x);
              return;
            }
          }
          else {
            return;
          }
        }
        else {
          return;
        }
      }
    }
    static void propagate(pointer ptr) {
      pointer prev = nullptr;
      while (ptr) {
        ::std::swap(ptr->parent, prev);
        ::std::swap(ptr, prev);
      }
      while (prev) {
        prev->push();
        ::std::swap(prev->parent, ptr);
        ::std::swap(prev, ptr);
      }
    }
    pointer expose() {
      propagate(this);
      pointer x = this, prev = nullptr;
      while (x) {
        x->splay();
        x->right = prev;
        prev = x;
        x = x->parent;
      }
      splay();
      return prev;
    }
    bool exposed_just_before() const { return !static_cast<bool>(parent); }
    bool is_root() const { return !static_cast<bool>(left); }
    pointer splay_prev() {
      node_type temp;
      pointer subtree = &temp;
      pointer cur = left, cur_r;
      left = nullptr;
      while (cur->push(), cur_r = cur->right) {
        cur_r->push();
        if (cur_r->right) {
          cur_r->rotate_as_right(cur);
          cur_r->set_right_of(subtree);
          subtree = cur_r;
          cur = cur_r->right;
        }
        else {
          cur->set_right_of(subtree);
          subtree = cur;
          cur = cur_r;
          break;
        }
      }
      cur->parent = nullptr;
      if (cur->left)
        cur->left->set_right_of(subtree);
      if (temp.right)
        temp.right->set_left_of(cur);
      else
        cur->left = nullptr;
      set_right_of(cur);
      return cur;
    }
  };
  using pointer = node_type *;

  container_type nodes;

  pointer get_ptr(const size_type v) { return &nodes[v]; }
  size_type get_index(const pointer p) {
    return static_cast<size_type>(p - nodes.data());
  }

public:
  explicit rooted_trees(const size_type size) : nodes(size) {}

  bool empty() const { return nodes.empty(); }
  size_type size() const { return nodes.size(); }

  bool is_root(const size_type v) {
    assert(v < size());
    nodes[v].expose();
    return nodes[v].is_root();
  }
  bool is_connected(const size_type v, const size_type w) {
    assert(v < size());
    assert(w < size());
    if (v == w)
      return true;
    nodes[v].expose();
    nodes[w].expose();
    return !nodes[v].exposed_just_before();
  }
  size_type lca(const size_type v, const size_type w) {
    assert(v < size());
    assert(w < size());
    if (v == w)
      return v;
    nodes[v].expose();
    pointer ptr = nodes[w].expose();
    if (nodes[v].exposed_just_before())
      return size();
    if (!static_cast<bool>(ptr))
      return w;
    return get_index(ptr);
  }
  size_type parent(const size_type v) {
    assert(v < size());
    nodes[v].expose();
    if (nodes[v].is_root())
      return size();
    else
      return get_index(nodes[v].splay_prev());
  }
  void reroot(const size_type v) {
    assert(v < size());
    nodes[v].expose();
    nodes[v].reverse();
  }
  void set_parent(const size_type v, const size_type p) {
    assert(v < size());
    assert(p < size());
    cut(v);
    assert(!is_connected(v, p));
    nodes[p].expose();
    nodes[p].set_left_of(get_ptr(v));
  }
  void cut(const size_type v) {
    assert(v < size());
    nodes[v].expose();
    nodes[v].cut_left();
  }

  ::std::vector<::std::pair<size_type, size_type>> all_edges() {
    ::std::vector<::std::pair<size_type, size_type>> ret;
    for (size_type i = static_cast<size_type>(0); i < size(); ++i) {
      const size_type p = parent(i);
      if (p != size())
        ret.emplace_back(p, i);
    }
    return ::std::move(ret);
  }
};
#include <cassert>
#include <cstddef>
#include <memory>
#include <utility>
#include <vector>

template <class ValueMonoid, class OperatorMonoid, class Modifier>
class lazy_st_trees {
public:
  using value_structure = ValueMonoid;
  using value_type = typename value_structure::value_type;
  using operator_structure = OperatorMonoid;
  using operator_type = typename operator_structure::value_type;
  using modifier = Modifier;

private:
  class node_type {
  public:
    node_type* left, * right, * parent;
    typename lazy_st_trees::value_type value, sum;
    typename lazy_st_trees::operator_type lazy;
    bool reversed; // reverse->lazy
    node_type(node_type* const p)
      : left(p), right(p), parent(p), value(value_structure::identity()),
      sum(value_structure::identity()),
      lazy(operator_structure::identity()), reversed(0) {}
  };

  using container_type = ::std::vector<node_type>;

public:
  using size_type = typename container_type::size_type;

private:
  using pointer = node_type *;
  using const_pointer = const node_type*;

  static void reverse(const pointer ptr) {
    ptr->lazy = operator_structure::reverse(::std::move(ptr->lazy));
    ptr->reversed ^= 1;
  }
  static void push(const pointer ptr) {
    if (ptr->reversed) {
      ptr->reversed = 0;
      ptr->value = value_structure::reverse(::std::move(ptr->value));
      ::std::swap(ptr->left, ptr->right);
      reverse(ptr->left);
      reverse(ptr->right);
    }
    ptr->left->lazy = operator_structure::operation(ptr->left->lazy, ptr->lazy);
    ptr->right->lazy =
      operator_structure::operation(ptr->right->lazy, ptr->lazy);
    ptr->value = modifier::operation(ptr->value, ptr->lazy);
    ptr->lazy = operator_structure::identity();
  }
  void propagate(pointer ptr) {
    pointer prev = nullptr;
    while (ptr != nil()) {
      ::std::swap(ptr->parent, prev);
      ::std::swap(ptr, prev);
    }
    while (prev) {
      push(prev);
      ::std::swap(prev->parent, ptr);
      ::std::swap(prev, ptr);
    }
    nil()->sum = value_structure::identity();
    nil()->lazy = operator_structure::identity();
    nil()->reversed = 0;
  }
  static value_type reflect(const const_pointer ptr) {
    return modifier::operation(
      ptr->reversed ? value_structure::reverse(ptr->sum) : ptr->sum,
      ptr->lazy);
  }
  static void calc(const pointer ptr) {
    ptr->sum = value_structure::operation(
      value_structure::operation(reflect(ptr->left), ptr->value),
      reflect(ptr->right));
  }
  static void rotate_l(const pointer ptr, const pointer ch) {
    ptr->right = ch->left;
    ch->left->parent = ptr;
    calc(ptr);
    ch->left = ptr;
    ptr->parent = ch;
  }
  static void rotate_r(const pointer ptr, const pointer ch) {
    ptr->left = ch->right;
    ch->right->parent = ptr;
    calc(ptr);
    ch->right = ptr;
    ptr->parent = ch;
  }
  static void splay(const pointer ptr) {
    for (pointer x, y = ptr;;) {
      x = ptr->parent;
      if (x->left == y) {
        y = x->parent;
        ptr->parent = y->parent;
        if (y->left == x)
          rotate_r(y, x), rotate_r(x, ptr);
        else if (y->right == x)
          rotate_l(y, ptr), rotate_r(x, ptr);
        else
          return ptr->parent = y, rotate_r(x, ptr);
      }
      else if (x->right == y) {
        y = x->parent;
        ptr->parent = y->parent;
        if (y->right == x)
          rotate_l(y, x), rotate_l(x, ptr);
        else if (y->left == x)
          rotate_r(y, ptr), rotate_l(x, ptr);
        else
          return ptr->parent = y, rotate_l(x, ptr);
      }
      else {
        return;
      }
    }
  }
  void expose(const pointer ptr) {
    propagate(ptr);
    pointer x = ptr, prev = nil();
    while (x != nil()) {
      splay(x);
      x->right = prev;
      calc(x);
      prev = x;
      x = x->parent;
    }
    splay(ptr);
    calc(ptr);
  }
  void reroot(const pointer ptr) {
    expose(ptr);
    reverse(ptr);
  }

  container_type nodes;

  pointer get_ptr(const size_type v) { return nodes.data() + v; }
  pointer nil() { return &nodes.back(); }

public:
  lazy_st_trees() : nodes() {}
  explicit lazy_st_trees(const size_type size) : nodes() {
    nodes.reserve(size + 1);
    nodes.resize(size + 1, node_type(nodes.data() + size));
  }

  bool empty() const { return size() == 0; }
  size_type size() const { return nodes.size() - 1; }

  bool connected(const size_type v, const size_type u) {
    assert(v < size());
    assert(u < size());
    expose(get_ptr(v));
    expose(get_ptr(u));
    return nodes[v].parent != nil() || v == u;
  }
  value_type fold_path(const size_type v, const size_type u) {
    assert(v < size());
    assert(u < size());
    assert(connected(v, u));
    reroot(get_ptr(v));
    expose(get_ptr(u));
    return nodes[u].sum;
  }

  void link(const size_type parent, const size_type child) {
    assert(parent < size());
    assert(child < size());
    assert(!connected(parent, child));
    reroot(get_ptr(child));
    nodes[child].parent = get_ptr(parent);
  }
  void cut(const size_type v) {
    assert(v < size());
    expose(get_ptr(v));
    nodes[v].left->parent = nil();
    nodes[v].left = nil();
    nodes[v].sum = nodes[v].value;
  }
  void update_path(const size_type v, const size_type u,
    const operator_type& value) {
    assert(v < size());
    assert(u < size());
    assert(connected(v, u));
    reroot(get_ptr(v));
    expose(get_ptr(u));
    nodes[u].lazy = value;
  }
  template <class F> void update_vertex(const size_type v, const F& f) {
    assert(v < size());
    expose(get_ptr(v));
    nodes[v].value = f(::std::move(nodes[v].value));
    calc(get_ptr(v));
  }
};

#include <tuple>

class trivial_group {
public:
  using value_type = std::tuple<>;
  static constexpr value_type operation(const value_type,
    const value_type) noexcept {
    return value_type();
  }
  static constexpr value_type identity() noexcept { return value_type(); }
  static constexpr value_type inverse(const value_type) noexcept {
    return value_type();
  }
  static constexpr value_type reverse(const value_type) noexcept {
    return value_type();
  }
};

template <class T> class trivial_action {
public:
  static constexpr typename T::value_type
    operation(const typename T::value_type& lhs,
      const typename trivial_group::value_type) noexcept {
    return lhs;
  }
};
template <class T> class plus_monoid {
public:
  using value_type = T;
  static value_type operation(const value_type& x, const value_type& y) {
    return x + y;
  }
  static value_type identity() { return value_type(0); }
  static value_type reverse(const value_type& x) { return x; }
};
#include <algorithm>
#include <iostream>
#include <utility>

namespace n91 {

  void main_() {
    const usize n = scan<usize>();
    lazy_st_trees<plus_monoid<u64>, trivial_group, trivial_action<plus_monoid<u64>>> lst(n *
      2_z);
    auto g = md_vec(n, 0_z, usize());
    for (const auto i : rep(0_z, n - 1_z)) {
      const usize u = scan<usize>();
      const usize v = scan<usize>();
      const u64 w = scan<u64>();
      g[u].push_back(v);
      g[v].push_back(u);
      lst.link(u, n+i);
      lst.link(n+i, v);
      lst.update_vertex(n+i, [&](auto) { return w; });
    }
    std::vector<usize> et(n);
    {
      usize cnt = 0_z;
      const auto dfs = [&](const auto& dfs, const usize v,
        const usize p) -> void {
          et[v] = cnt++;
          for (const auto e : g[v]) {
            if (e != p) {
              dfs(dfs, e, v);
            }
          }
      };
      dfs(dfs, 0_z, n);
    }
    const usize q = scan<usize>();
    for (const auto i : rep(0_z, q)) {
      const usize k = 3_z;
      std::vector<usize> x(k);
      for (auto& e : x) {
        std::cin >> e;
      }
      std::sort(x.begin(), x.end(),
        [&](usize l, usize r) { return et[l] < et[r]; });
      u64 ans = static_cast<u64>(0);
      for (const auto i : rep(0_z, k)) {
        ans += lst.fold_path(x[i], x[(i + 1_z) % k]);
      }
      std::cout << ans / static_cast<u64>(2) << std::endl;
    }
  }

} // namespace n91

int main() {
  n91::main_();
  return 0;
}
yukicoder

結果

テストケース

ソースコード
