#538519 (C++17) No.1197 モンスターショー

提出ソース

結果

問題	No.1197 モンスターショー
ユーザー	KoD
提出日時	2020-08-22 17:54:57
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	7,010 bytes
コンパイル時間	1,229 ms
コンパイル使用メモリ	94,892 KB
実行使用メモリ	20,612 KB
最終ジャッジ日時	2024-10-15 11:47:33
合計ジャッジ時間	9,987 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	WA	-
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	TLE	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-
testcase_20	--	-
testcase_21	--	-
testcase_22	--	-
testcase_23	--	-
testcase_24	--	-
testcase_25	--	-
testcase_26	--	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-

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

ソースコード

raw source code

#line 1 "main.cpp"

/**
 * @title Template
 */

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

#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/chmin_chmax.cpp"

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

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

/**
 * @title Chmin/Chmax
 */
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/range.cpp"

#line 4 "/Users/kodamankod/Desktop/Programming/Library/other/range.cpp"

class range {
public:
  class iterator {
  private:
    int64_t M_position;

  public:
    constexpr iterator(int64_t position) noexcept: M_position(position) { }
    constexpr void operator ++ () noexcept { ++M_position; }
    constexpr bool operator != (iterator other) const noexcept { return M_position != other.M_position; }
    constexpr int64_t operator * () const noexcept { return M_position; }

  };

  class reverse_iterator {
  private:
    int64_t M_position;
  
  public:
    constexpr reverse_iterator(int64_t position) noexcept: M_position(position) { }
    constexpr void operator ++ () noexcept { --M_position; }
    constexpr bool operator != (reverse_iterator other) const noexcept { return M_position != other.M_position; }
    constexpr int64_t operator * () const noexcept { return M_position; }

  };
  
private:
  const iterator M_first, M_last;

public:
  constexpr range(int64_t first, int64_t last) noexcept: M_first(first), M_last(std::max(first, last)) { }
  constexpr iterator begin() const noexcept { return M_first; }
  constexpr iterator end() const noexcept { return M_last; }
  constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator(*M_last - 1); } 
  constexpr reverse_iterator rend() const noexcept { return reverse_iterator(*M_first - 1); } 

};

/**
 * @title Range
 */
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/rev.cpp"

#include <type_traits>
#include <iterator>
#line 6 "/Users/kodamankod/Desktop/Programming/Library/other/rev.cpp"

template <class T>
class rev_impl {
public:
  using iterator = decltype(std::rbegin(std::declval<T>()));

private:
  const iterator M_begin;
  const iterator M_end;

public:
  constexpr rev_impl(T &&cont) noexcept: M_begin(std::rbegin(cont)), M_end(std::rend(cont)) { }
  constexpr iterator begin() const noexcept { return M_begin; }
  constexpr iterator end() const noexcept { return M_end; }

};

template <class T>
constexpr decltype(auto) rev(T &&cont) {
  return rev_impl<T>(std::forward<T>(cont));
}

/**
 * @title Reverser
 */
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/fix_point.cpp"

#line 4 "/Users/kodamankod/Desktop/Programming/Library/other/fix_point.cpp"

template <class Func>
struct fix_point_impl: private Func {
  explicit constexpr fix_point_impl(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)...);
  }
};

template <class Func>
constexpr decltype(auto) fix_point(Func &&func) {
  return fix_point_impl<Func>(std::forward<Func>(func));
}

/**
 * @title Lambda Recursion
 */
#line 18 "main.cpp"

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;

constexpr i32 Bucket = 150;

struct query_type {
  i32 vertex, index;
  query_type(): vertex(0), index(0) { }
};

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  i32 N, K, Q;
  std::cin >> N >> K >> Q;
  std::vector<i32> C(K);
  for (auto &x: C) {
    std::cin >> x;
    --x;
  }
  std::vector<std::vector<i32>> graph(N);
  for (auto i: range(1, N)) {
    i32 u, v;
    std::cin >> u >> v;
    --u; --v;
    graph[u].push_back(v);
    graph[v].push_back(u);
  }

  std::vector<std::array<i32, 17>> parent(N);
  std::vector<i32> depth(N);
  fix_point([&](auto dfs, i32 u, i32 p) -> void {
    if (p == -1) {
      depth[u] = 0;
      parent[u][0] = u;
    } 
    else {
      depth[u] = depth[p] + 1;
      parent[u][0] = p;
    }
    for (auto v: graph[u]) {
      if (v != p) {
        dfs(v, u);
      }
    }
  })(0, -1);
  for (auto j: range(0, 16)) {
    for (auto i: range(0, N)) {
      parent[i][j + 1] = parent[parent[i][j]][j];
    }
  }
  
  auto lca = [&](i32 u, i32 v) {
    if (depth[u] > depth[v]) {
      std::swap(u, v);
    }
    auto dif = depth[v] - depth[u];
    for (auto j: range(0, 17)) {
      if (dif & 1) {
        v = parent[v][j];
      }
      dif >>= 1;
    }
    if (u == v) {
      return u;
    }
    for (auto j: rev(range(0, 17))) {
      if (parent[u][j] != parent[v][j]) {
        u = parent[u][j];
        v = parent[v][j];
      }
    }
    return parent[u][0];
  };
  auto calc = [&](i32 u, i32 v) {
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
  };

  std::vector<query_type> query(Q);
  std::vector<i64> answer;
  for (auto &[v, i]: query) {
    i32 type;
    std::cin >> type;
    if (type == 1) {
      std::cin >> i >> v;
      --i; --v;
    }
    else {
      std::cin >> v;
      --v;
      answer.push_back(0);
      i = -((i32) answer.size());
    }
  }

  const i32 Block = (Q + Bucket - 1) / Bucket;

  for (auto steps: range(0, Block)) {
    const i32 first = steps * Bucket;
    const i32 last = std::min<i32>((steps + 1) * Bucket, Q);

    std::vector<i64> size(N), dist(N);
    std::vector<bool> stable(K, true);
    std::vector<i32> indices;
    for (auto i: range(first, last)) {
      if (query[i].index >= 0) {
        indices.push_back(query[i].index);
        stable[query[i].index] = false;
      }
    }
    for (auto i: range(0, K)) {
      if (stable[i]) {
        ++size[C[i]];
      } 
    }

    fix_point([&](auto dfs, i32 u, i32 p) -> void {
      for (auto v: graph[u]) {
        if (v != p) {
          dfs(v, u);
          size[u] += size[v];
          dist[u] += dist[v] + size[v];
        }
      }
    })(0, -1);

    fix_point([&](auto dfs, i32 u, i32 p, i64 s, i64 d) -> void {
      size[u] += s;
      dist[u] += s + d;
      for (auto v: graph[u]) {
        if (v != p) {
          dfs(v, u, size[u] - size[v], dist[u] - (size[v] + dist[v]));
        }
      }
    })(0, -1, 0, 0);

    // for (auto i: range(0, N)) {
    //   std::cout << size[i] << ' ' << dist[i] << '\n';
    // }

    for (auto i: range(first, last)) {
      if (query[i].index >= 0) {
        C[query[i].index] = query[i].vertex;
      }
      else {
        const auto j = -(query[i].index + 1);
        answer[j] += dist[query[i].vertex];
        for (auto k: indices) {
          answer[j] += calc(query[i].vertex, C[k]);
        }
      }
    }

  }

  for (auto x: answer) {
    std::cout << x << '\n';
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード