結果
問題 | No.900 aδδitivee |
ユーザー | たこし |
提出日時 | 2019-10-04 22:56:29 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 387 ms / 2,000 ms |
コード長 | 4,424 bytes |
コンパイル時間 | 2,400 ms |
コンパイル使用メモリ | 209,548 KB |
実行使用メモリ | 33,024 KB |
最終ジャッジ日時 | 2024-10-03 08:21:56 |
合計ジャッジ時間 | 12,473 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 14 ms
22,016 KB |
testcase_01 | AC | 14 ms
22,016 KB |
testcase_02 | AC | 15 ms
22,016 KB |
testcase_03 | AC | 14 ms
22,016 KB |
testcase_04 | AC | 14 ms
22,144 KB |
testcase_05 | AC | 14 ms
22,144 KB |
testcase_06 | AC | 15 ms
22,016 KB |
testcase_07 | AC | 381 ms
27,648 KB |
testcase_08 | AC | 386 ms
27,648 KB |
testcase_09 | AC | 381 ms
27,648 KB |
testcase_10 | AC | 379 ms
27,640 KB |
testcase_11 | AC | 380 ms
27,660 KB |
testcase_12 | AC | 384 ms
27,648 KB |
testcase_13 | AC | 384 ms
27,776 KB |
testcase_14 | AC | 384 ms
27,724 KB |
testcase_15 | AC | 380 ms
27,596 KB |
testcase_16 | AC | 384 ms
27,776 KB |
testcase_17 | AC | 382 ms
27,648 KB |
testcase_18 | AC | 378 ms
27,660 KB |
testcase_19 | AC | 385 ms
27,648 KB |
testcase_20 | AC | 382 ms
27,584 KB |
testcase_21 | AC | 387 ms
27,624 KB |
testcase_22 | AC | 351 ms
32,936 KB |
testcase_23 | AC | 348 ms
32,840 KB |
testcase_24 | AC | 352 ms
33,024 KB |
testcase_25 | AC | 350 ms
32,840 KB |
testcase_26 | AC | 355 ms
32,872 KB |
testcase_27 | AC | 357 ms
32,896 KB |
testcase_28 | AC | 358 ms
32,992 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define INF 100000000 #define YJ 1145141919 #define INF_INT_MAX 2147483647 #define INF_LL 9223372036854775 #define INF_LL_MAX 9223372036854775807 #define EPS 1e-10 #define MOD 1000000007 #define MOD9 998244353 #define Pi acos(-1) #define LL long long #define ULL unsigned long long #define LD long double #define int long long using II = pair<int, int>; int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; } int lcm(int a, int b) { return a * b / gcd(a, b); } int extgcd(int a, int b, int &x, int &y) { int g = a; x = 1; y = 0; if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x; return g; } #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define ALL(a) begin((a)), end((a)) #define RALL(a) (a).rbegin(), (a).rend() #define PB push_back #define MP make_pair #define SZ(a) int((a).size()) class RangeNode { public: RangeNode() { init(); } void init() { delay = delayFlag = 0; val = 0; } //クエリ処理 static int evaluateQuery(int p1, int p2) { return p1 + p2; } //range処理 void evaluateRange() { val += delay * rangeSum; } //delay処理 void evaluateDelay(int d) { delay += d; } //単位元(クエリ処理) static int unit() { return 0; } int val; int delay; bool delayFlag; int rangeSum = 0; }; template<class T, int Size> class RangeSegmentTree { public: RangeSegmentTree() { init(); } void init() { n = 1; while(n < Size) n *= 2; node.clear(); node.resize(2*n); } void setRangeSum() { for(int p = 2*n-1; 0 <= p; p--) { // cerr << p << " " << node[p].rangeSum << endl; if(p == 0) break; node[(p-1)/2].rangeSum += node[p].rangeSum; } } void evaluateRangeNode(int k, int l, int r) { if(node[k].delayFlag) { node[k].evaluateRange(); if(r-l>1) { node[2*k+1].evaluateDelay(node[k].delay); node[2*k+2].evaluateDelay(node[k].delay); node[2*k+1].delayFlag = node[2*k+2].delayFlag = true; } node[k].delayFlag = false; node[k].delay = 0; } } void updateRange(int l, int r, int v) { _updateRange(l,r,v,0,0,n); } int query(int l, int r) { return _query(l,r,0,0,n); } vector<T> node; int n; void _updateRange(int l, int r, int v, int k, int a, int b) { evaluateRangeNode(k,a,b); if(b <= l || r <= a) return; else if(l <= a && b <= r) { node[k].evaluateDelay(v); node[k].delayFlag = true; evaluateRangeNode(k,a,b); return; } else { int mid = (a+b)/2; _updateRange(l,r,v,2*k+1,a,mid); _updateRange(l,r,v,2*k+2,mid,b); node[k].val = RangeNode::evaluateQuery(node[2*k+1].val, node[2*k+2].val); return; } } int _query(int l, int r, int k, int a, int b) { evaluateRangeNode(k,a,b); if(b <= l || r <= a) return RangeNode::unit(); else if(l <= a && b <= r) { return node[k].val; } else { int mid = (a+b)/2; int vl = _query(l,r,2*k+1,a,mid); int vr = _query(l,r,2*k+2,mid,b); return RangeNode::evaluateQuery(vl,vr); } } }; const int MAX_N = 100005; int N; vector<II> Edge[MAX_N]; RangeSegmentTree<RangeNode, 2*MAX_N> rgt; int INDEX[2*MAX_N]; int first[MAX_N], last[MAX_N]; void setRangeSegmentTree(int pos, int& index) { first[pos] = index; for(II edge : Edge[pos]) { rgt.node[rgt.n-1 + index].rangeSum = 1; INDEX[index++] = pos; setRangeSegmentTree(edge.first, index); } if(pos != 0) rgt.node[rgt.n-1 + index].rangeSum = -1; last[pos] = index; INDEX[index++] = pos; } void setWeight(int pos, int& index) { for(II edge : Edge[pos]) { int next = edge.first; int w = edge.second; rgt.updateRange(index, index+1, w); index++; setWeight(next, index); rgt.updateRange(index-1, index, w); } index++; } signed main() { cin >> N; REP(n,N-1) { int u, v, w; cin >> u >> v >> w; Edge[u].push_back(II(v,w)); } rgt.init(); int index = 0; setRangeSegmentTree(0, index); rgt.setRangeSum(); index = 0; setWeight(0, index); int Q; cin >> Q; REP(q,Q) { int a; cin >> a; if(a == 1) { int b, c; cin >> b >> c; rgt.updateRange(first[b], last[b], c); } else { int b; cin >> b; cout << rgt.query(0,first[b]) << endl; } } return 0; }