結果
問題 | No.900 aδδitivee |
ユーザー | 0w1 |
提出日時 | 2019-10-10 23:27:49 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 243 ms / 2,000 ms |
コード長 | 2,522 bytes |
コンパイル時間 | 2,830 ms |
コンパイル使用メモリ | 223,616 KB |
実行使用メモリ | 26,772 KB |
最終ジャッジ日時 | 2024-11-22 03:07:37 |
合計ジャッジ時間 | 10,835 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 14 ms
16,512 KB |
testcase_01 | AC | 12 ms
16,512 KB |
testcase_02 | AC | 14 ms
16,512 KB |
testcase_03 | AC | 14 ms
16,512 KB |
testcase_04 | AC | 14 ms
16,512 KB |
testcase_05 | AC | 14 ms
16,512 KB |
testcase_06 | AC | 14 ms
16,512 KB |
testcase_07 | AC | 243 ms
22,240 KB |
testcase_08 | AC | 225 ms
22,396 KB |
testcase_09 | AC | 234 ms
22,272 KB |
testcase_10 | AC | 231 ms
22,264 KB |
testcase_11 | AC | 228 ms
22,392 KB |
testcase_12 | AC | 234 ms
22,392 KB |
testcase_13 | AC | 226 ms
22,272 KB |
testcase_14 | AC | 230 ms
22,380 KB |
testcase_15 | AC | 234 ms
22,392 KB |
testcase_16 | AC | 231 ms
22,272 KB |
testcase_17 | AC | 224 ms
22,400 KB |
testcase_18 | AC | 238 ms
22,260 KB |
testcase_19 | AC | 227 ms
22,392 KB |
testcase_20 | AC | 231 ms
22,388 KB |
testcase_21 | AC | 225 ms
22,268 KB |
testcase_22 | AC | 219 ms
26,644 KB |
testcase_23 | AC | 206 ms
26,644 KB |
testcase_24 | AC | 218 ms
26,644 KB |
testcase_25 | AC | 208 ms
26,772 KB |
testcase_26 | AC | 208 ms
26,648 KB |
testcase_27 | AC | 205 ms
26,644 KB |
testcase_28 | AC | 205 ms
26,772 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; template<int n> struct Segt { int64_t atag[n << 2]; int64_t sums[n << 2]; int64_t sumv[n << 2]; Segt(vector<int> s) { s.resize(n); function<void(int, int, int)> build = [&](int lb, int rb, int t) { atag[t] = 0; sumv[t] = 0; if (rb - lb == 1) return void(sums[t] = s[lb]); int mb = lb + rb >> 1; build(lb, mb, t << 1); build(mb, rb, t << 1 | 1); sums[t] = sums[t << 1] + sums[t << 1 | 1]; }; build(0, n, 1); } void push(int t) { if (atag[t]) { for (int c = 0; c < 2; ++c) { atag[t << 1 | c] += atag[t]; sumv[t << 1 | c] += sums[t << 1 | c] * atag[t]; } atag[t] = 0; } } void add(int v, int ql, int qr, int lb = 0, int rb = n, int t = 1) { if (qr <= lb || rb <= ql) return; if (ql <= lb && rb <= qr) { atag[t] += v; sumv[t] += sums[t] * v; return; } push(t); int mb = lb + rb >> 1; add(v, ql, qr, lb, mb, t << 1); add(v, ql, qr, mb, rb, t << 1 | 1); sumv[t] = sumv[t << 1] + sumv[t << 1 | 1]; } int64_t query(int ql, int qr, int lb = 0, int rb = n, int t = 1) { if (qr <= lb || rb <= ql) return 0; if (ql <= lb && rb <= qr) return sumv[t]; push(t); int mb = lb + rb >> 1; return query(ql, qr, lb, mb, t << 1) + query(ql, qr, mb, rb, t << 1 | 1); } }; int main() { ios::sync_with_stdio(false); int N; cin >> N; vector<vector<pair<int, int>>> G(N); for (int i = 0; i < N - 1; ++i) { int U, V, W; cin >> U >> V >> W; G[U].emplace_back(W, V); } vector<int> lb(N); vector<int> rb(N); vector<int> sgn(2 * N); { int ctr = 0; lb[0] = ctr++; function<void(int)> dfs = [&](int u) { for (int i = 0; i < G[u].size(); ++i) { int w, v; tie(w, v) = G[u][i]; lb[v] = ctr++; sgn[lb[v]] = +1; dfs(v); rb[v] = ctr++; sgn[rb[v]] = -1; } }; dfs(0); rb[0] = ctr; } static Segt<(1 << 18)> tree(sgn); for (int u = 0; u < N; ++u) { for (int i = 0; i < G[u].size(); ++i) { int w, v; tie(w, v) = G[u][i]; tree.add(w, lb[v], lb[v] + 1); tree.add(w, rb[v], rb[v] + 1); } } int Q; cin >> Q; while (Q--) { int P; cin >> P; if (P == 1) { int A, X; cin >> A >> X; tree.add(X, lb[A] + 1, rb[A]); } else { int B; cin >> B; cout << tree.query(0, lb[B] + 1) << endl; } } return 0; }