結果
問題 | No.1216 灯籠流し/Lanterns |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
//#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 n91int main() {n91::main_();return 0;}