結果
| 問題 |
No.900 aδδitivee
|
| コンテスト | |
| ユーザー |
 MarcusAureliusAntoninus
|
| 提出日時 | 2019-10-05 00:18:49 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 365 ms / 2,000 ms |
| コード長 | 4,228 bytes |
| コンパイル時間 | 3,924 ms |
| コンパイル使用メモリ | 213,352 KB |
| 最終ジャッジ日時 | 2025-01-07 20:54:35 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 27 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:116:31: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 4 has type ‘int64_t*’ {aka ‘long int*’} [-Wformat=]
116 | scanf("%d%d%lld", &u, &v, &w);
| ~~~^ ~~
| | |
| | int64_t* {aka long int*}
| long long int*
| %ld
main.cpp:147:36: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘long int’ [-Wformat=]
147 | printf("%lld\n", rasqEdge.get(0, indicesBegin[b]) + rasqRev.get(0, revIndicesBegin[b]));
| ~~~^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| | |
| long long int long int
| %ld
main.cpp:110:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
110 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
main.cpp:116:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
116 | scanf("%d%d%lld", &u, &v, &w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:131:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
131 | scanf("%d", &Q);
| ~~~~~^~~~~~~~~~
main.cpp:135:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
135 |
ソースコード
#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);
}
}