結果
問題 | No.900 aδδitivee |
ユーザー | ngtkana |
提出日時 | 2019-10-04 23:09:36 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 255 ms / 2,000 ms |
コード長 | 7,918 bytes |
コンパイル時間 | 2,643 ms |
コンパイル使用メモリ | 217,840 KB |
実行使用メモリ | 28,800 KB |
最終ジャッジ日時 | 2024-04-14 11:36:23 |
合計ジャッジ時間 | 9,780 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 251 ms
21,248 KB |
testcase_08 | AC | 246 ms
21,120 KB |
testcase_09 | AC | 249 ms
21,248 KB |
testcase_10 | AC | 249 ms
21,248 KB |
testcase_11 | AC | 250 ms
21,120 KB |
testcase_12 | AC | 251 ms
21,248 KB |
testcase_13 | AC | 248 ms
21,052 KB |
testcase_14 | AC | 243 ms
21,248 KB |
testcase_15 | AC | 252 ms
21,248 KB |
testcase_16 | AC | 253 ms
21,248 KB |
testcase_17 | AC | 255 ms
21,120 KB |
testcase_18 | AC | 251 ms
21,120 KB |
testcase_19 | AC | 248 ms
21,248 KB |
testcase_20 | AC | 248 ms
21,248 KB |
testcase_21 | AC | 245 ms
21,148 KB |
testcase_22 | AC | 212 ms
28,672 KB |
testcase_23 | AC | 211 ms
28,740 KB |
testcase_24 | AC | 211 ms
28,800 KB |
testcase_25 | AC | 217 ms
28,800 KB |
testcase_26 | AC | 214 ms
28,800 KB |
testcase_27 | AC | 217 ms
28,592 KB |
testcase_28 | AC | 216 ms
28,800 KB |
ソースコード
#include <bits/stdc++.h> #define loop(n) for (int ngtkana_is_genius = 0; ngtkana_is_genius < int(n); ngtkana_is_genius++) #define rep(i, begin, end) for(int i = int(begin); i < int(end); i++) #define all(v) v.begin(), v.end() #define rand(l, r) std::uniform_int_distribution<>(l, r)(mt) using lint = long long; auto cmn = [](auto& a, auto b){if (a > b) {a = b; return true;} return false;}; auto cmx = [](auto& a, auto b){if (a < b) {a = b; return true;} return false;}; void debug_impl() { std::cerr << std::endl; } template <typename Head, typename... Tail> void debug_impl(Head head, Tail... tail){ std::cerr << " " << head; debug_impl(tail...); } #ifndef STOPIT #define debug(...)\ std::cerr << std::boolalpha << "[" << #__VA_ARGS__ << "]:";\ debug_impl(__VA_ARGS__);\ std::cerr << std::noboolalpha; #else #define debug 0; #endif template <typename T> auto make_vector_impl(size_t sz, T t) {return std::vector<T>(sz, t);} template <size_t N, typename T, typename U, std::enable_if_t<N == 1, std::nullptr_t> = nullptr> auto make_vector(size_t sz, U u) {return make_vector_impl(sz, T(u));} template <size_t N, typename T, std::enable_if_t<N == 1, std::nullptr_t> = nullptr> auto make_vector(size_t sz) {return std::vector<T>(sz);} template <size_t N, typename T, typename... Args, std::enable_if_t<N != 1, std::nullptr_t> = nullptr> auto make_vector(size_t a, Args... args) {return make_vector_impl(a, make_vector<N - 1, T>(args...));} template <typename T, typename Size_t> auto& at(T& t, Size_t i) {return t.at(i);} template <typename T, typename Size_t, typename... Args> auto& at(T& t, Size_t i, Args... args) {return at(t.at(i), args...);} template < typename Container, typename Value = typename Container::value_type, std::enable_if_t<!std::is_same< Container, std::string >::value, std::nullptr_t> = nullptr> std::istream& operator>> (std::istream& is, Container& v) { for (auto & x : v) { is >> x; } return is; } template < typename Container, typename Value = typename Container::value_type, std::enable_if_t<!std::is_same< Container, std::string >::value, std::nullptr_t> = nullptr > std::ostream& operator<< (std::ostream& os, Container const& v) { os << "{"; for (auto it = v.begin(); it != v.end(); it++) {os << (it != v.begin() ? "," : "") << *it;} return os << "}"; } template < template < typename ... > class Tuple, typename... Args, std::size_t ... Inds, std::size_t = std::tuple_size< Tuple < Args ... > >::value > std::istream& tuple_input_impl(std::istream& os, Tuple<Args...>& tuple, std::integer_sequence<std::size_t, Inds...>) { (void)std::initializer_list<int>{((void)(os >> std::get< Inds >(tuple)), 0)...}; return os; } template < template < typename ... > class Tuple, typename... Args, std::size_t = std::tuple_size< Tuple < Args ... > >::value > std::istream& operator>> (std::istream& os, Tuple<Args...>& tuple) { return tuple_input_impl(os, tuple, std::index_sequence_for<Args...>()); } template < template < typename ... > class Tuple, typename... Args, std::size_t ... Inds, std::size_t = std::tuple_size< Tuple < Args ... > >::value > std::ostream& tuple_output_impl(std::ostream& os, const Tuple<Args...>& tuple, std::integer_sequence<std::size_t, Inds...>) { os << "("; (void)std::initializer_list<int>{((void)(os << (Inds > 0 ? "," : "") << std::get< Inds >(tuple)), 0)...}; return os << ")"; } template < template < typename ... > class Tuple, typename... Args, std::size_t = std::tuple_size< Tuple < Args ... > >::value > std::ostream& operator<< (std::ostream& os, const Tuple<Args...>& tuple) { return tuple_output_impl(os, tuple, std::index_sequence_for<Args...>()); } template<typename Value, typename BinaryOp> class segment_tree { int sz, n, N; BinaryOp op; Value id; std::vector<Value> table; auto& op_eq(Value& x, Value y) const { return x = op(x, y); } void merge(int u) { table.at(u) = op(table.at(2 * u), table.at(2 * u + 1)); } Value query_impl(int l, int r, int k, int L, int R) const { return l <= L && R <= r ? table.at(k) : R <= l || r <= L ? id : op( query_impl(l, r, 2 * k, L, (L + R) / 2), query_impl(l, r, 2 * k + 1, (L + R) / 2, R) ); } public: segment_tree(int sz, BinaryOp op, Value id): sz (sz), n (std::pow(2, int(std::log2(2 * sz - 1)))), N (n * 2), op (op), id (id), table (N, id) {} auto& at(int i) { return table.at(n + i); } auto& at(int i) const { return table.at(n + i); } auto collect() const { auto ret = std::vector<Value>(sz); for (auto i = 0; i < sz; i++) { ret.at(i) = at(i); } return ret; } auto query(int l, int r) const { return query_impl(l, r, 1, 0, n); } void build_oneline(int i) { for (i += n, i /= 2; i > 0; i /= 2) merge(i); } void build() { for (auto i = 1; i < n; i++) merge(i); } void update (int u, Value val) { at(u) = val; build_oneline(u); } void add (int u, Value val) { at(u) += val; build_oneline(u); } }; template<typename Value, typename BinaryOp> auto make_segment_tree(int sz, BinaryOp op, Value id) { return segment_tree<Value, BinaryOp>(sz, std::move(op), id); } template< typename F > class fixed_point : F { public: explicit constexpr fixed_point (F&& f) noexcept : F(std::forward< F >(f)) {} template< typename ... Args > constexpr decltype(auto) operator()(Args&& ... args) const { return F::operator()(*this, std::forward< Args >(args)...); } }; template< typename F > static inline constexpr decltype(auto) fix (F&& f) noexcept { return fixed_point< F >{std::forward< F >(f)}; } int main() { std::cin.tie(0); std::cin.sync_with_stdio(false); int n; std::cin >> n; auto graph = make_vector< 2, std::pair< int, lint > >(n, 0); loop(n - 1) { int u, v, w; std::cin >> u >> v >> w; graph.at(u).emplace_back(v, w); graph.at(v).emplace_back(u, w); } // queries int q; std::cin >> q; std::vector< std::tuple< int, int, int > > queries(q); std::vector< std::vector< int > > query_inds(n); rep(i, 0, n) { int c; std::cin >> c; if (c == 1) { int a, x; std::cin >> a >> x; queries.at(i) = {1, a, x}; query_inds.at(a).emplace_back(i); } else { int b; std::cin >> b; queries.at(i) = {2, b, -1}; query_inds.at(b).emplace_back(i); } } auto a = make_segment_tree( n, [](auto x, auto y){ return x + y; }, 0LL ); auto b = a; auto add = [&] (auto&& qids, int sign, int d) { for (auto qid : qids) { int c, u; lint x; std::tie(c, u, x) = queries.at(qid); if (c == 1) { a.add(qid, -d * x * sign); b.add(qid, x * sign); } } }; std::vector< lint > ans(q, -1); auto answer = [&] (auto&& qids, int d, lint wd) { for (auto qid : qids) { int c, u; lint x; std::tie(c, u, x) = queries.at(qid); if (c == 2) { auto f = a.query(0, qid); auto g = b.query(0, qid) * d; auto h = wd; // debug(a.collect()); // debug(b.collect()); // debug("answer", u, qid, f, g, h); // std::cout << std::endl; ans.at(qid) = a.query(0, qid) + b.query(0, qid) * d + wd; } } }; auto root = 0; fix ([&](auto&& dfs, int crr, int prv, int d, lint wd) -> void { auto const & qids = query_inds.at(crr); answer(qids, d, wd); add(qids, +1, d); for (auto const& e : graph.at(crr)) { int nxt; lint w; std::tie(nxt, w) = e; if (nxt == prv) continue; dfs(nxt, crr, d + 1, wd + w); } add(qids, -1, d); })(root, root, 0, 0); rep(i, 0, q) { if (std::get< 0 >(queries.at(i)) == 2) { std::cout << ans.at(i) << std::endl; } } return 0; }