結果
問題 | No.900 aδδitivee |
ユーザー | MarcusAureliusAntoninus |
提出日時 | 2019-10-05 00:18:49 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 268 ms / 2,000 ms |
コード長 | 4,228 bytes |
コンパイル時間 | 4,024 ms |
コンパイル使用メモリ | 218,700 KB |
実行使用メモリ | 26,236 KB |
最終ジャッジ日時 | 2023-07-26 22:58:31 |
合計ジャッジ時間 | 11,608 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,376 KB |
testcase_06 | AC | 1 ms
4,376 KB |
testcase_07 | AC | 263 ms
22,128 KB |
testcase_08 | AC | 264 ms
22,260 KB |
testcase_09 | AC | 262 ms
22,148 KB |
testcase_10 | AC | 253 ms
22,068 KB |
testcase_11 | AC | 265 ms
22,248 KB |
testcase_12 | AC | 266 ms
22,068 KB |
testcase_13 | AC | 251 ms
22,200 KB |
testcase_14 | AC | 263 ms
22,196 KB |
testcase_15 | AC | 264 ms
22,332 KB |
testcase_16 | AC | 254 ms
22,068 KB |
testcase_17 | AC | 249 ms
22,140 KB |
testcase_18 | AC | 259 ms
22,072 KB |
testcase_19 | AC | 268 ms
22,252 KB |
testcase_20 | AC | 252 ms
22,152 KB |
testcase_21 | AC | 256 ms
22,152 KB |
testcase_22 | AC | 219 ms
26,168 KB |
testcase_23 | AC | 213 ms
26,104 KB |
testcase_24 | AC | 214 ms
26,020 KB |
testcase_25 | AC | 209 ms
26,036 KB |
testcase_26 | AC | 215 ms
26,236 KB |
testcase_27 | AC | 212 ms
26,112 KB |
testcase_28 | AC | 207 ms
26,208 KB |
ソースコード
#include <bits/stdc++.h> struct Edge { int to; int64_t dist{1}; }; using EdgeVec = std::vector<Edge>; using EdgeLists = std::vector<EdgeVec>; /////////////////////////////// // Range Add Range Sum Query // /////////////////////////////// template<typename T = int64_t> class RAddRSumQ { private: // ノードの番号、左端、右端 using NodeInfo = std::array<int, 3>; std::vector<T> added_container_, sum_container_; void build(const unsigned int array_size) { unsigned int length{1}; while (length < array_size) length <<= 1; added_container_.resize(2 * length); sum_container_.resize(2 * length); } // 二つの半開区間[left1,right1)と[left2,right2)の重複する区間の要素数を求める int overlapRange(const int left1, const int right1, const int left2, const int right2) const { return std::max(0, std::min(right1, right2) - std::max(left1, left2)); } // nodeの子ノードをpre_addedにpushする void pushNext(std::stack<NodeInfo> &pre_added, const NodeInfo &node) { const int mid{(node[1] + node[2]) >> 1}; pre_added.push({2 * node[0] + 1, mid, node[2]}); pre_added.push({2 * node[0], node[1], mid}); } public: RAddRSumQ(const unsigned int array_size) { build(array_size); } RAddRSumQ(const std::vector<T> &array) { build(array.size()); std::copy(array.begin(), array.end(), added_container_.begin() + (added_container_.size() >> 1)); std::copy(array.begin(), array.end(), sum_container_.begin() + (sum_container_.size() >> 1)); for (auto i{(sum_container_.size() >> 1) - 1}; i > 0; i--) sum_container_[i] = sum_container_[2 * i] + sum_container_[2 * i + 1]; } // [left,right)の半開区間(0-indexed)にaddedを加算 void update(const int left, const int right, const T added) { std::stack<NodeInfo> pre_added; pre_added.push({1, 0, (int)sum_container_.size() >> 1}); while (!pre_added.empty()) { NodeInfo node{pre_added.top()}; pre_added.pop(); const int add_range{overlapRange(node[1], node[2], left, right)}; if (add_range == 0) continue; sum_container_[node[0]] += add_range * added; if (add_range == node[2] - node[1]) added_container_[node[0]] += added; else pushNext(pre_added, node); } } // left,rightは0-indexed、[left, right)の半開区間 T get(const int left, const int right) { std::stack<NodeInfo> pre_added; pre_added.push({1, 0, (int)sum_container_.size() >> 1}); T sum{}; while (!pre_added.empty()) { NodeInfo node{pre_added.top()}; pre_added.pop(); const int add_range{overlapRange(node[1], node[2], left, right)}; if (add_range == 0) continue; if (add_range == node[2] - node[1]) sum += sum_container_[node[0]]; else { sum += add_range * added_container_[node[0]]; pushNext(pre_added, node); } } return sum; } }; EdgeLists edges; std::vector<int64_t> depth, revDepth; std::vector<int> indicesBegin, indicesEnd, revIndicesBegin, revIndicesEnd; std::vector<bool> visited; void dfs(int); int main() { int N; scanf("%d", &N); edges.resize(N); for (int i{}; i < N - 1; i++) { int u, v; int64_t w; scanf("%d%d%lld", &u, &v, &w); edges[u].push_back({v, w}); edges[v].push_back({u, w}); } indicesBegin.resize(N); indicesEnd.resize(N); revIndicesBegin.resize(N); revIndicesEnd.resize(N); visited.resize(N); dfs(0); indicesEnd[0] = depth.size(); revIndicesEnd[0] = revDepth.size(); RAddRSumQ<> rasqEdge(depth), rasqRev(revDepth); int Q; scanf("%d", &Q); for (int i{}; i < Q; i++) { int query; scanf("%d", &query); if (query == 1) { int a, x; scanf("%d%d", &a, &x); rasqEdge.update(indicesBegin[a], indicesEnd[a], x); rasqRev.update(revIndicesBegin[a], revIndicesEnd[a], -x); } else { int b; scanf("%d", &b); printf("%lld\n", rasqEdge.get(0, indicesBegin[b]) + rasqRev.get(0, revIndicesBegin[b])); } } return 0; } void dfs(int index) { visited[index] = true; for (auto& e: edges[index]) { if (visited[e.to]) continue; depth.push_back(e.dist); indicesBegin[e.to] = depth.size(); revIndicesBegin[e.to] = revDepth.size(); dfs(e.to); indicesEnd[e.to] = depth.size(); revIndicesEnd[e.to] = revDepth.size(); revDepth.push_back(-e.dist); } }