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

提出ソース

結果

問題	No.1197 モンスターショー
ユーザー	KoD
提出日時	2020-08-22 18:09:02
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	12,174 bytes
コンパイル時間	1,312 ms
コンパイル使用メモリ	98,440 KB
実行使用メモリ	24,628 KB
最終ジャッジ日時	2024-04-23 11:59:01
合計ジャッジ時間	39,155 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 24,628 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	1 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	2 ms 5,376 KB
testcase_06	AC	1 ms 5,376 KB
testcase_07	AC	491 ms 20,736 KB
testcase_08	AC	240 ms 10,368 KB
testcase_09	AC	971 ms 15,476 KB
testcase_10	AC	2,227 ms 15,756 KB
testcase_11	AC	928 ms 8,276 KB
testcase_12	AC	408 ms 6,272 KB
testcase_13	AC	367 ms 11,312 KB
testcase_14	AC	1,399 ms 12,360 KB
testcase_15	AC	860 ms 8,292 KB
testcase_16	AC	2,041 ms 18,084 KB
testcase_17	AC	1,915 ms 18,280 KB
testcase_18	AC	642 ms 8,832 KB
testcase_19	AC	1,917 ms 15,540 KB
testcase_20	AC	219 ms 7,680 KB
testcase_21	AC	774 ms 6,004 KB
testcase_22	AC	53 ms 5,376 KB
testcase_23	AC	1,864 ms 13,192 KB
testcase_24	AC	1,105 ms 12,544 KB
testcase_25	AC	439 ms 9,600 KB
testcase_26	AC	1,001 ms 10,332 KB
testcase_27	AC	1,214 ms 16,596 KB
testcase_28	AC	1,245 ms 11,020 KB
testcase_29	AC	614 ms 12,064 KB
testcase_30	AC	352 ms 13,184 KB
testcase_31	AC	615 ms 11,008 KB
testcase_32	AC	663 ms 5,376 KB
testcase_33	AC	324 ms 9,344 KB
testcase_34	TLE	-
testcase_35	TLE	-
testcase_36	TLE	-
testcase_37	TLE	-
testcase_38	TLE	-
testcase_39	TLE	-
testcase_40	TLE	-
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 2 "/Users/kodamankod/Desktop/Programming/Library/other/fast_io.cpp"

#include <cstddef>
#include <cstdint>
#include <cstring>
#line 7 "/Users/kodamankod/Desktop/Programming/Library/other/fast_io.cpp"

namespace fast_io {
  static constexpr size_t buf_size = 1 << 18;
  static constexpr size_t buf_margin = 1;
  static constexpr size_t block_size = 10000;
  static constexpr size_t integer_size = 20;

  static char inbuf[buf_size + buf_margin] = {};
  static char outbuf[buf_size + buf_margin] = {};
  static char block_str[block_size * 4 + buf_margin] = {};

  static constexpr uint64_t power10[] = {
    1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000,
    1000000000, 10000000000, 100000000000, 1000000000000, 10000000000000,
    100000000000000, 1000000000000000, 10000000000000000, 100000000000000000,
    1000000000000000000, 10000000000000000000u
  };

  class scanner {
  private:
    size_t M_in_pos = 0, M_in_end = buf_size;

    void M_load() { 
      M_in_end = fread(inbuf, 1, buf_size, stdin); 
      inbuf[M_in_end] = '\0';  
    }
    void M_reload() {
      size_t length = M_in_end - M_in_pos;
      memmove(inbuf, inbuf + M_in_pos, length);
      M_in_end = length + fread(inbuf + length, 1, buf_size - length, stdin);
      inbuf[M_in_end] = '\0';
      M_in_pos = 0;
    }

    void M_ignore_space() {
      while (inbuf[M_in_pos] <= ' ') {
        if (__builtin_expect(++M_in_pos == M_in_end, 0)) M_reload();
      }
    }

    char M_next() { return inbuf[M_in_pos++]; }
    char M_next_nonspace() {
      M_ignore_space();
      return inbuf[M_in_pos++];
    }

  public:
    scanner() { M_load(); }
    
    void scan(char &c) { c = M_next_nonspace(); }
    void scan(std::string &s) {
      M_ignore_space();
      s = "";
      do {
        size_t start = M_in_pos;
        while (inbuf[M_in_pos] > ' ') ++M_in_pos;
        s += std::string(inbuf + start, inbuf + M_in_pos);
        if (inbuf[M_in_pos] != '\0') break;
        M_reload();
      } while (true);
    }

    template <class T>
    typename std::enable_if<std::is_integral<T>::value, void>::type scan(T &x) {
      char c = M_next_nonspace();
      if (__builtin_expect(M_in_pos + integer_size >= M_in_end, 0)) M_reload();
      bool n = false;
      if (c == '-') n = true, x = 0;
      else x = c & 15;
      while ((c = M_next()) >= '0') x = x * 10 + (c & 15);
      if (n) x = -x;
    }

    template <class T, class... Args>
    void scan(T &x, Args&... args) {
      scan(x); scan(args...);
    }

    template <class T>
    scanner& operator >> (T &x) {
      scan(x); return *this;
    }

  };

  class printer {
  private:
    size_t M_out_pos = 0;

    void M_flush() {
      fwrite(outbuf, 1, M_out_pos, stdout);
      M_out_pos = 0;
    }

    void M_precompute() {
      for (size_t i = 0; i < block_size; ++i) {
        size_t j = 4, k = i;
        while (j--) {
          block_str[i * 4 + j] = k % 10 + '0';
          k /= 10;
        }
      }
    }

    static constexpr size_t S_integer_digits(uint64_t n) {
      if (n >= power10[10]) {
        if (n >= power10[19]) return 20;
        if (n >= power10[18]) return 19;
        if (n >= power10[17]) return 18;
        if (n >= power10[16]) return 17;
        if (n >= power10[15]) return 16;
        if (n >= power10[14]) return 15;
        if (n >= power10[13]) return 14;
        if (n >= power10[12]) return 13;
        if (n >= power10[11]) return 12;
        return 11;
      }
      else {
        if (n >= power10[9]) return 10;
        if (n >= power10[8]) return 9;
        if (n >= power10[7]) return 8;
        if (n >= power10[6]) return 7;
        if (n >= power10[5]) return 6;
        if (n >= power10[4]) return 5;
        if (n >= power10[3]) return 4;
        if (n >= power10[2]) return 3;
        if (n >= power10[1]) return 2;
        return 1;
      }
    }

  public:
    printer() { M_precompute(); }
    ~printer() { M_flush(); }

    void print(char c) { 
      outbuf[M_out_pos++] = c;
      if (__builtin_expect(M_out_pos == buf_size, 0)) M_flush();
    }
    void print(const char *s) {
      while (*s != 0) {
        outbuf[M_out_pos++] = *s++;
        if (M_out_pos == buf_size) M_flush();
      }
    }
    void print(const std::string &s) {
      for (auto c: s) {
        outbuf[M_out_pos++] = c;
        if (M_out_pos == buf_size) M_flush();
      }
    }
    
    template <class T>
    typename std::enable_if<std::is_integral<T>::value, void>::type print(T x) {
      if (__builtin_expect(M_out_pos + integer_size >= buf_size, 0)) M_flush();
      if (x < 0) print('-'), x = -x;
      size_t digit = S_integer_digits(x);
      size_t len = digit;
      while (len >= 4) {
        len -= 4;
        memcpy(outbuf + M_out_pos + len, block_str + (x % block_size) * 4, 4);
        x /= 10000;
      }
      memcpy(outbuf + M_out_pos, block_str + x * 4 + 4 - len, len);
      M_out_pos += digit;
    }

    template <class T, class... Args>
    void print(const T &x, const Args&... args) {
      print(x); print(' '); print(args...);
    }

    template <class... Args>
    void println(const Args&... args) {
      print(args...); print('\n');
    }

    template <class T>
    printer& operator << (const T &x) {
      print(x); return *this;
    }

  };

};

/**
 * @title Fast Input/Output
 */
#line 19 "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 = 400;

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

fast_io::scanner cin;
fast_io::printer cout;

int main() {

  i32 N, K, Q;
  cin >> N >> K >> Q;
  std::vector<i32> C(K);
  for (auto &x: C) {
    cin >> x;
    --x;
  }
  std::vector<std::vector<i32>> graph(N);
  for (auto i: range(1, N)) {
    i32 u, v;
    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;
    cin >> type;
    if (type == 1) {
      cin >> i >> v;
      --i; --v;
    }
    else {
      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) {
        stable[query[i].index] = false;
      }
    }
    for (auto i: range(0, K)) {
      if (stable[i]) {
        ++size[C[i]];
      } 
      else {
        indices.push_back(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(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) {
    cout << x << '\n';
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード