結果

問題 No.1216 灯籠流し/Lanterns
ユーザー noshi91noshi91
提出日時 2020-08-30 14:17:03
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 1,843 ms / 4,500 ms
コード長 5,443 bytes
コンパイル時間 2,190 ms
コンパイル使用メモリ 159,560 KB
実行使用メモリ 138,200 KB
最終ジャッジ日時 2023-08-09 12:21:54
合計ジャッジ時間 43,694 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,384 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 74 ms
23,956 KB
testcase_05 AC 926 ms
79,916 KB
testcase_06 AC 55 ms
11,520 KB
testcase_07 AC 812 ms
69,732 KB
testcase_08 AC 835 ms
53,172 KB
testcase_09 AC 324 ms
35,248 KB
testcase_10 AC 391 ms
33,668 KB
testcase_11 AC 156 ms
27,680 KB
testcase_12 AC 61 ms
19,392 KB
testcase_13 AC 203 ms
37,584 KB
testcase_14 AC 123 ms
27,588 KB
testcase_15 AC 231 ms
36,360 KB
testcase_16 AC 214 ms
43,600 KB
testcase_17 AC 1,339 ms
77,460 KB
testcase_18 AC 281 ms
38,280 KB
testcase_19 AC 1,694 ms
123,832 KB
testcase_20 AC 664 ms
68,368 KB
testcase_21 AC 296 ms
45,628 KB
testcase_22 AC 1,259 ms
93,464 KB
testcase_23 AC 104 ms
31,596 KB
testcase_24 AC 104 ms
15,492 KB
testcase_25 AC 43 ms
10,656 KB
testcase_26 AC 722 ms
56,268 KB
testcase_27 AC 189 ms
32,724 KB
testcase_28 AC 131 ms
30,296 KB
testcase_29 AC 312 ms
47,784 KB
testcase_30 AC 530 ms
56,076 KB
testcase_31 AC 1,119 ms
79,624 KB
testcase_32 AC 477 ms
59,264 KB
testcase_33 AC 106 ms
24,804 KB
testcase_34 AC 953 ms
83,240 KB
testcase_35 AC 1,118 ms
87,424 KB
testcase_36 AC 676 ms
88,732 KB
testcase_37 AC 1,843 ms
135,080 KB
testcase_38 AC 1,680 ms
134,808 KB
testcase_39 AC 1,088 ms
82,680 KB
testcase_40 AC 1,035 ms
86,244 KB
testcase_41 AC 1,122 ms
86,256 KB
testcase_42 AC 1,063 ms
86,120 KB
testcase_43 AC 1,034 ms
86,308 KB
testcase_44 AC 1,093 ms
86,244 KB
testcase_45 AC 1,494 ms
137,844 KB
testcase_46 AC 1,761 ms
138,164 KB
testcase_47 AC 1,529 ms
138,200 KB
testcase_48 AC 1,757 ms
137,860 KB
testcase_49 AC 1,506 ms
137,600 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