#505020 (C++17) No.1030 だんしんぐぱーりない

提出ソース

結果

問題	No.1030 だんしんぐぱーりない
ユーザー	KoD
提出日時	2020-06-30 20:38:04
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	412 ms / 2,000 ms
コード長	7,805 bytes
コンパイル時間	1,274 ms
コンパイル使用メモリ	98,264 KB
実行使用メモリ	18,432 KB
最終ジャッジ日時	2024-09-13 08:55:13
合計ジャッジ時間	12,358 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	307 ms 15,872 KB
testcase_06	AC	246 ms 13,184 KB
testcase_07	AC	162 ms 7,808 KB
testcase_08	AC	168 ms 8,960 KB
testcase_09	AC	262 ms 16,128 KB
testcase_10	AC	113 ms 6,940 KB
testcase_11	AC	258 ms 10,368 KB
testcase_12	AC	278 ms 14,336 KB
testcase_13	AC	224 ms 13,312 KB
testcase_14	AC	296 ms 13,312 KB
testcase_15	AC	142 ms 6,944 KB
testcase_16	AC	263 ms 11,392 KB
testcase_17	AC	268 ms 16,364 KB
testcase_18	AC	323 ms 13,824 KB
testcase_19	AC	178 ms 6,940 KB
testcase_20	AC	209 ms 9,856 KB
testcase_21	AC	211 ms 12,672 KB
testcase_22	AC	212 ms 10,240 KB
testcase_23	AC	245 ms 9,600 KB
testcase_24	AC	194 ms 6,944 KB
testcase_25	AC	220 ms 9,728 KB
testcase_26	AC	154 ms 6,940 KB
testcase_27	AC	173 ms 6,944 KB
testcase_28	AC	277 ms 12,160 KB
testcase_29	AC	214 ms 14,080 KB
testcase_30	AC	198 ms 10,496 KB
testcase_31	AC	199 ms 9,728 KB
testcase_32	AC	257 ms 13,184 KB
testcase_33	AC	272 ms 15,104 KB
testcase_34	AC	117 ms 6,940 KB
testcase_35	AC	402 ms 18,316 KB
testcase_36	AC	412 ms 18,304 KB
testcase_37	AC	402 ms 18,432 KB
testcase_38	AC	400 ms 18,304 KB
testcase_39	AC	405 ms 18,368 KB
testcase_40	AC	2 ms 6,940 KB
testcase_41	AC	2 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>

template <class T, class U>
inline bool chmin(T &lhs, const U &rhs) {
  if (lhs > rhs) { lhs = rhs; return true; }
  return false;
}

template <class T, class U>
inline bool chmax(T &lhs, const U &rhs) {
  if (lhs < rhs) { lhs = rhs; return true; }
  return false;
}

struct range {
  using itr = int64_t;
  struct iterator {
    itr i;
    constexpr iterator(itr i_) noexcept : i(i_) { }
    constexpr void operator ++ () noexcept { ++i; }
    constexpr itr operator * () const noexcept { return i; }
    constexpr bool operator != (iterator x) const noexcept { return i != x.i; }
  };
  const iterator l, r;
  constexpr range(itr l_, itr r_) noexcept : l(l_), r(std::max(l_, r_)) { }
  constexpr iterator begin() const noexcept { return l; }
  constexpr iterator end() const noexcept { return r; }
};

struct revrange {
  using itr = int64_t;
  struct iterator {
    itr i;
    constexpr iterator(itr i_) noexcept : i(i_) { }
    constexpr void operator ++ () noexcept { --i; }
    constexpr itr operator * () const noexcept { return i; }
    constexpr bool operator != (iterator x) const noexcept { return i != x.i; }
  };
  const iterator l, r;
  constexpr revrange(itr l_, itr r_) noexcept : l(l_ - 1), r(std::max(l_, r_) - 1) { }
  constexpr iterator begin() const noexcept { return r; }
  constexpr iterator end() const noexcept { return l; }
};

class heavy_light_decomposition {
public:
  using size_type = int32_t;

private:
  std::vector<std::vector<size_type>> graph;
  std::vector<size_type> size, parent, head;
  size_type index;

  void calc_size(size_type u, size_type p) {
    size[u] = 1;
    for (size_type v: graph[u]) {
      if (v != p) {
        calc_size(v, u);
        size[u] += size[v];
      }
    }
  }

  void decompose(size_type u, size_type p, size_type h) {
    label[u] = index;
    head[u] = h;
    parent[u] = p;
    ++index;
    size_type max = -1, heavy = -1;
    for (size_type v : graph[u]) {
      if (v != p) {
        if (max < size[v]) {
          max = size[v];
          heavy = v;
        }
      }
    }
    if (heavy == -1) {
      return;
    }
    decompose(heavy, u, h);
    for (size_type v : graph[u]) {
      if (v != p && v != heavy) {
        decompose(v, u, v);
      }
    }
  }

public:
  std::vector<size_type> label;

  heavy_light_decomposition() { }
  heavy_light_decomposition(size_type size_) { init(size_); }

  void init(size_type size_) {
    graph.assign(size_, { });
    size.assign(size_, 0);
    parent.assign(size_, 0);
    head.assign(size_, 0);
    label.assign(size_, 0);
  }

  void add_edge(size_type u, size_type v) {
    graph[u].push_back(v);
    graph[v].push_back(u);
  }

  void build() {
    index = 0;
    calc_size(0, -1);
    decompose(0, -1, 0);
  }

  template <class T> 
  void each_edge(size_type u, size_type v, const T &func) const {
    while (true) {
      if (label[u] > label[v]) {
        std::swap(u, v);
      }
      if (head[u] == head[v]) {
        if (label[u] + 1 <= label[v]) {
          func(label[u] + 1, label[v]);
        }
        return;
      }
      func(label[head[v]], label[v]);
      v = parent[head[v]];
    }
  }

  template <class T> 
  void each_vertex(size_type u, size_type v, const T &func) const {
    while (true) {
      if (label[u] > label[v]) {
        std::swap(u, v);
      }
      if (head[u] == head[v]) {
        func(label[u], label[v]);
        return;
      }
      func(label[head[v]], label[v]);
      v = parent[head[v]];
    }
  }

  size_type lca(size_type u, size_type v) const {
    if (label[u] > label[v]) {
      std::swap(u, v);
    }
    while (label[u] <= label[v]) {
      if (head[u] == head[v]) {
        return u;
      }
      v = parent[head[v]];
    }
    return v;
  }

};

template <class Monoid>
class segment_tree {
public:
  using monoid     = Monoid;
  using value_type = typename Monoid::type;
  using size_type  = size_t;

private:
  std::vector<value_type> M_tree;

  void M_fix_change(const size_type index) {
    M_tree[index] = monoid::operation(M_tree[index << 1 | 0], M_tree[index << 1 | 1]);
  }

public:
  segment_tree() = default;
  explicit segment_tree(const size_type size) { initialize(size); }
  template <class InputIterator>
  explicit segment_tree(InputIterator first, InputIterator last) { construct(first, last); }

  void initialize(const size_type size) {
    clear();
    M_tree.assign(size << 1, monoid::identity());
  }

  template <class InputIterator>
  void construct(InputIterator first, InputIterator last) {
    clear();
    const size_type size = std::distance(first, last);
    M_tree.reserve(size << 1);
    M_tree.assign(size, monoid::identity());
    std::copy(first, last, std::back_inserter(M_tree));
    for (size_type index = size - 1; index != 0; --index) {
      M_fix_change(index);
    }
  }

  void assign(size_type index, const value_type &value) {
    index += size();
    M_tree[index] = value;
    while (index != 1) {
      index >>= 1;
      M_fix_change(index);
    } 
  }

  const value_type& at(size_type index) const { 
    return M_tree[index + size()];
  }

  value_type fold(size_type first, size_type last) const {
    first += size();
    last += size();
    value_type fold_l = monoid::identity();
    value_type fold_r = monoid::identity();
    while (first != last) {
      if (first & 1) {
        fold_l = monoid::operation(fold_l, M_tree[first]);
        ++first;
      }
      if (last & 1) {
        --last;
        fold_r = monoid::operation(M_tree[last], fold_r);      
      }
      first >>= 1;
      last  >>= 1;
    }
    return monoid::operation(fold_l, fold_r);
  }

  void clear() {
    M_tree.clear();
    M_tree.shrink_to_fit();
  }

  size_type size() const { 
    return M_tree.size() >> 1;
  }

};

using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;

constexpr i32 inf32 = (i32(1) << 30) - 1;
constexpr i64 inf64 = (i64(1) << 62) - 1;

template <class Func>
struct fix_point: private Func {
  explicit constexpr fix_point(Func &&func): Func(std::forward<Func>(func)) { }
  template <class... Args>
  constexpr decltype(auto) operator () (Args &&... args) const {
    return Func::operator()(*this, std::forward<Args>(args)...);
  }
};

struct monoid {
  static inline heavy_light_decomposition *hld = nullptr;
  using type = std::pair<i32, bool>;
  static type identity() { return { 0, false}; }
  static type operation(const type& v1, const type& v2) { 
    if (!v1.second) return v2;
    if (!v2.second) return v1;
    return { hld -> lca(v1.first, v2.first), true };
  }
};

int main() {
  i32 N, K, Q;
  std::cin >> N >> K >> Q;
  std::vector<i32> vivace(N);
  std::vector<std::vector<i32>> graph(N);
  for (auto &x: vivace) {
    std::cin >> x;
  }
  std::vector<i32> lives(K);
  for (i32 &x: lives) {
    std::cin >> x;
    --x;
  }
  heavy_light_decomposition hld(N);
  monoid::hld = &hld;
  for (auto i: range(0, N - 1)) {
    i32 a, b;
    std::cin >> a >> b;
    --a; --b;
    graph[a].push_back(b);
    graph[b].push_back(a);
    hld.add_edge(a, b);
  }
  hld.build();
  segment_tree<monoid> seg(K);
  for (i32 i: range(0, K)) {
    seg.assign(i, { lives[i], true });
  }
  fix_point([&](auto dfs, i32 u, i32 p) -> void {
    if (p != -1) {
      chmax(vivace[u], vivace[p]);
    }
    for (auto v: graph[u]) {
      if (v != p) {
        dfs(v, u);
      }
    }
  })(0, -1);
  while (Q--) {
    i32 type;
    std::cin >> type;
    if (type == 1) {
      i32 x, y;
      std::cin >> x >> y;
      --x; --y;
      seg.assign(x, { y, true });
    }
    else {
      i32 l, r;
      std::cin >> l >> r;
      --l;
      std::cout << vivace[seg.fold(l, r).first] << '\n';
    }
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード