結果

問題 No.1216 灯籠流し/Lanterns
ユーザー noshi91noshi91
提出日時 2020-08-30 14:17:03
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,747 ms / 4,500 ms
コード長 5,443 bytes
コンパイル時間 3,250 ms
コンパイル使用メモリ 161,384 KB
実行使用メモリ 138,352 KB
最終ジャッジ日時 2024-11-15 07:33:35
合計ジャッジ時間 40,619 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 AC 77 ms
24,124 KB
testcase_05 AC 891 ms
80,144 KB
testcase_06 AC 54 ms
11,904 KB
testcase_07 AC 767 ms
69,800 KB
testcase_08 AC 782 ms
53,316 KB
testcase_09 AC 315 ms
35,460 KB
testcase_10 AC 352 ms
33,860 KB
testcase_11 AC 156 ms
28,072 KB
testcase_12 AC 62 ms
19,556 KB
testcase_13 AC 198 ms
37,656 KB
testcase_14 AC 115 ms
27,704 KB
testcase_15 AC 216 ms
36,604 KB
testcase_16 AC 209 ms
43,624 KB
testcase_17 AC 1,207 ms
77,696 KB
testcase_18 AC 255 ms
38,376 KB
testcase_19 AC 1,628 ms
123,664 KB
testcase_20 AC 624 ms
68,328 KB
testcase_21 AC 283 ms
45,692 KB
testcase_22 AC 1,185 ms
93,776 KB
testcase_23 AC 105 ms
31,820 KB
testcase_24 AC 86 ms
15,488 KB
testcase_25 AC 41 ms
10,988 KB
testcase_26 AC 659 ms
56,576 KB
testcase_27 AC 182 ms
32,952 KB
testcase_28 AC 128 ms
30,616 KB
testcase_29 AC 295 ms
47,860 KB
testcase_30 AC 490 ms
56,588 KB
testcase_31 AC 1,063 ms
79,840 KB
testcase_32 AC 451 ms
59,360 KB
testcase_33 AC 110 ms
25,168 KB
testcase_34 AC 907 ms
83,172 KB
testcase_35 AC 1,013 ms
87,688 KB
testcase_36 AC 643 ms
88,896 KB
testcase_37 AC 1,738 ms
135,128 KB
testcase_38 AC 1,703 ms
134,884 KB
testcase_39 AC 1,049 ms
83,044 KB
testcase_40 AC 955 ms
86,252 KB
testcase_41 AC 1,016 ms
86,256 KB
testcase_42 AC 973 ms
86,252 KB
testcase_43 AC 987 ms
86,388 KB
testcase_44 AC 1,051 ms
86,372 KB
testcase_45 AC 1,469 ms
138,212 KB
testcase_46 AC 1,747 ms
138,352 KB
testcase_47 AC 1,501 ms
137,964 KB
testcase_48 AC 1,739 ms
137,968 KB
testcase_49 AC 1,518 ms
137,968 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#define NDEBUG

#pragma region cp_template

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>

namespace n91 {

using i32 = std::int32_t;
using i64 = std::int64_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

struct rep {
  struct itr {
    usize i;
    constexpr itr(const usize i) noexcept : i(i) {}
    void operator++() noexcept { ++i; }
    constexpr usize operator*() const noexcept { return i; }
    constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
  };
  const itr f, l;
  constexpr rep(const usize f, const usize l) noexcept
      : f(std::min(f, l)), l(l) {}
  constexpr auto begin() const noexcept { return f; }
  constexpr auto end() const noexcept { return l; }
};
struct revrep {
  struct itr {
    usize i;
    constexpr itr(const usize i) noexcept : i(i) {}
    void operator++() noexcept { --i; }
    constexpr usize operator*() const noexcept { return i; }
    constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
  };
  const itr f, l;
  constexpr revrep(const usize f, const usize l) noexcept
      : f(l - 1), l(std::min(f, l) - 1) {}
  constexpr auto begin() const noexcept { return f; }
  constexpr auto end() const noexcept { return 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) noexcept {
  return a < b ? b - a : a - b;
}
template <class T> void chmin(T &a, const T &b) noexcept {
  if (b < a)
    a = b;
}
template <class T> void chmax(T &a, const T &b) noexcept {
  if (a < b)
    a = b;
}
template <class F> class rec_lambda {
  F f;

public:
  rec_lambda(F &&f) : f(std::move(f)) {}
  template <class... Args> auto operator()(Args &&... args) const {
    return f(*this, std::forward<Args>(args)...);
  }
};
template <class F> auto make_rec(F &&f) { return rec_lambda<F>(std::move(f)); }
template <class T> T scan() {
  T ret;
  std::cin >> ret;
  return ret;
}
constexpr char eoln = '\n';
template <class T> T ceildiv(const T &l, const T &r) {
  return l / r + (l % r != 0 ? 1 : 0);
}

} // namespace n91

#pragma endregion cp_template

#include <functional>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

namespace n91 {

void main_() {
  using P = std::pair<u64, usize>;
  using os = tree<P, null_type, std::less<P>, rb_tree_tag,
                  tree_order_statistics_node_update>;
  /*
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  //*/
  const usize n = scan<usize>();
  const usize q = scan<usize>();
  struct edge_t {
    usize to;
    u64 c;
  };
  std::vector<std::vector<edge_t>> g(n);
  for (const usize i : rep(0, n - 1)) {
    const usize a = scan<usize>() - 1;
    const usize b = scan<usize>() - 1;
    const u64 c = scan<u64>();
    g[a].push_back({b, c});
    g[b].push_back({a, c});
  }
  struct query_t {
    int type;
    usize v;
    u64 t;
    u64 l;
    usize u;
  };
  std::vector<query_t> qs(q);
  for (auto &e : qs) {
    std::cin >> e.type >> e.v >> e.t >> e.l;
    --e.v;
  }
  std::vector<usize> in(n), out(n);
  std::vector<u64> depth(n);
  {
    std::vector<std::vector<usize>> qrev(n);
    for (const usize i : rep(0, q)) {
      if (qs[i].type == 0) {
        qrev[qs[i].v].push_back(i);
      }
    }
    usize time = 0;
    std::vector<u64> cur;
    std::vector<usize> cv;
    cur.push_back(0);
    cv.push_back(0);
    make_rec([&](const auto &dfs, const usize v, const usize p) -> void {
      in[v] = time++;
      for (const usize i : qrev[v]) {
        if (depth[v] <= qs[i].l) {
          qs[i].u = -1;
        } else {
          const usize x =
              std::lower_bound(cur.begin(), cur.end(), depth[v] - qs[i].l) -
              cur.begin() - 1;
          qs[i].u = cv[x];
        }
      }
      for (const auto &e : g[v]) {
        if (e.to == p) {
          continue;
        }
        depth[e.to] = depth[v] + e.c;
        cur.push_back(depth[e.to]);
        cv.push_back(e.to);
        dfs(e.to, v);
        cur.pop_back();
        cv.pop_back();
      }
      out[v] = time;
    })(0, n);
  }
  std::vector<os> add(n * 2), sub(n * 2);
  const auto ins = [&](auto &seg, usize i, P x) {
    i += n;
    while (i != 0) {
      seg[i].insert(x);
      i /= 2;
    }
  };
  const auto fold = [&](const auto &seg, usize l, usize r, P x) -> usize {
    l += n;
    r += n;
    usize ret = 0;
    while (l != r) {
      if (l % 2 != 0) {
        ret += seg[l].order_of_key(x);
        ++l;
      }
      l /= 2;
      if (r % 2 != 0) {
        --r;
        ret += seg[r].order_of_key(x);
      }
      r /= 2;
    }
    return ret;
  };
  for (const usize i : rep(0, q)) {
    const auto &e = qs[i];
    if (e.type == 0) {
      ins(add, in[e.v], {e.t + depth[e.v], i});
      if (e.u != -1) {
        ins(sub, in[e.u], {e.t + depth[e.v], i});
      }
    } else {
      usize ans = 0;
      ans += fold(add, in[e.v], out[e.v], {e.t + depth[e.v] + 1, 0});
      ans -= fold(sub, in[e.v], out[e.v], {e.t + depth[e.v] + 1, 0});
      std::cout << ans << eoln;
    }
  }
}

} // namespace n91

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