結果

問題 No.1216 灯籠流し/Lanterns
ユーザー noshi91
提出日時 2020-08-30 14:17:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,891 ms / 4,500 ms
コード長 5,443 bytes
コンパイル時間 3,261 ms
コンパイル使用メモリ 165,220 KB
最終ジャッジ日時 2025-01-13 21:44:09
ジャッジサーバーID
(参考情報)
judge3 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 48
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0