結果
問題 | No.900 aδδitivee |
ユーザー | 0w1 |
提出日時 | 2019-10-10 23:27:49 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 212 ms / 2,000 ms |
コード長 | 2,522 bytes |
コンパイル時間 | 2,723 ms |
コンパイル使用メモリ | 225,228 KB |
実行使用メモリ | 31,996 KB |
最終ジャッジ日時 | 2024-05-01 20:42:48 |
合計ジャッジ時間 | 9,816 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 8 ms
20,876 KB |
testcase_01 | AC | 9 ms
21,220 KB |
testcase_02 | AC | 9 ms
21,576 KB |
testcase_03 | AC | 8 ms
21,376 KB |
testcase_04 | AC | 9 ms
20,604 KB |
testcase_05 | AC | 9 ms
21,160 KB |
testcase_06 | AC | 8 ms
21,028 KB |
testcase_07 | AC | 204 ms
27,008 KB |
testcase_08 | AC | 199 ms
27,716 KB |
testcase_09 | AC | 212 ms
26,640 KB |
testcase_10 | AC | 204 ms
26,628 KB |
testcase_11 | AC | 199 ms
26,660 KB |
testcase_12 | AC | 201 ms
26,864 KB |
testcase_13 | AC | 198 ms
28,112 KB |
testcase_14 | AC | 204 ms
27,332 KB |
testcase_15 | AC | 199 ms
27,020 KB |
testcase_16 | AC | 209 ms
27,036 KB |
testcase_17 | AC | 199 ms
26,716 KB |
testcase_18 | AC | 206 ms
26,504 KB |
testcase_19 | AC | 197 ms
27,868 KB |
testcase_20 | AC | 197 ms
27,156 KB |
testcase_21 | AC | 197 ms
26,512 KB |
testcase_22 | AC | 183 ms
31,996 KB |
testcase_23 | AC | 187 ms
31,620 KB |
testcase_24 | AC | 184 ms
30,908 KB |
testcase_25 | AC | 186 ms
31,544 KB |
testcase_26 | AC | 178 ms
31,016 KB |
testcase_27 | AC | 184 ms
31,392 KB |
testcase_28 | AC | 191 ms
31,932 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; }