結果
問題 | No.900 aδδitivee |
ユーザー | kotatsugame |
提出日時 | 2019-10-12 03:53:38 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 344 ms / 2,000 ms |
コード長 | 2,744 bytes |
コンパイル時間 | 1,242 ms |
コンパイル使用メモリ | 93,716 KB |
実行使用メモリ | 27,160 KB |
最終ジャッジ日時 | 2023-08-17 13:36:06 |
合計ジャッジ時間 | 12,349 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,452 KB |
testcase_01 | AC | 3 ms
6,512 KB |
testcase_02 | AC | 3 ms
6,464 KB |
testcase_03 | AC | 3 ms
6,468 KB |
testcase_04 | AC | 3 ms
6,456 KB |
testcase_05 | AC | 2 ms
6,484 KB |
testcase_06 | AC | 3 ms
6,532 KB |
testcase_07 | AC | 302 ms
22,964 KB |
testcase_08 | AC | 306 ms
23,080 KB |
testcase_09 | AC | 306 ms
22,920 KB |
testcase_10 | AC | 301 ms
23,036 KB |
testcase_11 | AC | 303 ms
22,972 KB |
testcase_12 | AC | 306 ms
22,992 KB |
testcase_13 | AC | 303 ms
22,972 KB |
testcase_14 | AC | 302 ms
22,968 KB |
testcase_15 | AC | 301 ms
23,000 KB |
testcase_16 | AC | 300 ms
23,056 KB |
testcase_17 | AC | 328 ms
22,900 KB |
testcase_18 | AC | 314 ms
22,912 KB |
testcase_19 | AC | 299 ms
23,008 KB |
testcase_20 | AC | 318 ms
23,244 KB |
testcase_21 | AC | 296 ms
23,064 KB |
testcase_22 | AC | 329 ms
27,160 KB |
testcase_23 | AC | 344 ms
27,044 KB |
testcase_24 | AC | 340 ms
27,156 KB |
testcase_25 | AC | 332 ms
26,996 KB |
testcase_26 | AC | 331 ms
26,992 KB |
testcase_27 | AC | 336 ms
26,988 KB |
testcase_28 | AC | 339 ms
27,040 KB |
コンパイルメッセージ
main.cpp:98:1: 警告: ISO C++ では型の無い ‘main’ の宣言を禁止しています [-Wreturn-type] 98 | main() | ^~~~
ソースコード
#include<iostream> #include<vector> #include<queue> using namespace std; #include<vector> #include<functional> template<typename T> struct lazysegtree{ function<T(T,T)>calcfn,lazycalcfn; function<T(T,T,int,int)>updatefn; int n; T defvalue,lazydefvalue; vector<T>dat,lazy; vector<bool>lazyflag; lazysegtree(int n_=0,T defvalue_=0, function<T(T,T)>calcfn_=[](T a,T b){return a+b;}, function<T(T,T)>lazycalcfn_=[](T a,T b){return a+b;}, function<T(T,T,int,int)>updatefn_=[](T a,T b,int l,int r){return a+b*(r-l);}, T lazydefvalue_=0 ):defvalue(defvalue_),lazydefvalue(lazydefvalue_), calcfn(calcfn_),lazycalcfn(lazycalcfn_),updatefn(updatefn_) { n=1; while(n<n_)n<<=1; dat.assign(2*n-1,defvalue); lazy.assign(2*n-1,lazydefvalue); lazyflag.assign(2*n-1,false); } void copy(const vector<T>&v) { for(int i=0;i<v.size();i++)dat[i+n-1]=v[i]; for(int i=n-2;i>=0;i--)dat[i]=calcfn(dat[2*i+1],dat[2*i+2]); } void eval(int i,int l,int r) { if(lazyflag[i]) { dat[i]=updatefn(dat[i],lazy[i],l,r); if(r-l>1) { lazy[2*i+1]=lazycalcfn(lazy[2*i+1],lazy[i]); lazy[2*i+2]=lazycalcfn(lazy[2*i+2],lazy[i]); lazyflag[2*i+1]=lazyflag[2*i+2]=true; } lazy[i]=lazydefvalue; lazyflag[i]=false; } } void update(int a,int b,T x,int k=0,int l=0,int r=-1)//[a,b) { if(r<0)r=n; eval(k,l,r); if(b<=l||r<=a)return; else if(a<=l&&r<=b) { lazy[k]=lazycalcfn(lazy[k],x); lazyflag[k]=true; eval(k,l,r); } else { update(a,b,x,2*k+1,l,(l+r)/2); update(a,b,x,2*k+2,(l+r)/2,r); dat[k]=calcfn(dat[2*k+1],dat[2*k+2]); } } T query(int a,int b,int k=0,int l=0,int r=-1)//[a,b) { if(r<0)r=n; eval(k,l,r); if(b<=l||r<=a)return defvalue; else if(a<=l&&r<=b)return dat[k]; else return calcfn( query(a,b,2*k+1,l,(l+r)/2), query(a,b,2*k+2,(l+r)/2,r) ); } }; int N; vector<pair<int,int> >G[1<<17]; int L[1<<17],R[1<<17]; vector<long>A; vector<int>sign,sum; void dfs(int u,int p) { L[u]=A.size(); for(pair<int,int>q:G[u]) { if(q.first==p)continue; A.push_back(q.second); sign.push_back(1); dfs(q.first,u); A.push_back(-q.second); sign.push_back(-1); } R[u]=A.size(); } main() { cin>>N; for(int i=1;i<N;i++) { int u,v,w;cin>>u>>v>>w; G[u].push_back(make_pair(v,w)); G[v].push_back(make_pair(u,w)); } dfs(0,-1); sum.push_back(0); for(int s:sign)sum.push_back(sum.back()+s); lazysegtree<long>P(A.size(),0,[](long a,long b){return a+b;}, [](long a,long b){return a+b;}, [](long a,long b,int l,int r){return a+b*(sum[r]-sum[l]);}); P.copy(A); int Q;cin>>Q; for(;Q--;) { int q;cin>>q; if(q==1) { int a;long x; cin>>a>>x; P.update(L[a],R[a],x); } else { int b;cin>>b; cout<<P.query(0,L[b])<<endl; } } }