結果
| 問題 | No.235 めぐるはめぐる (5) |
| ユーザー |
 latte0119
|
| 提出日時 | 2015-10-31 16:06:47 |
| 言語 | C++11（廃止可能性あり） (gcc 13.3.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 3,960 bytes |
| コンパイル時間 | 877 ms |
| コンパイル使用メモリ | 70,900 KB |
| 実行使用メモリ | 60,820 KB |
| 最終ジャッジ日時 | 2024-09-13 06:22:40 |
| 合計ジャッジ時間 | 5,134 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | RE * 3 |
コンパイルメッセージ
main.cpp: In function ‘long long int hl_init()’:
main.cpp:108:1: warning: no return statement in function returning non-void [-Wreturn-type]
108 | }
| ^
main.cpp: In function ‘int main()’:
main.cpp:164:21: warning: format ‘%d’ expects argument of type ‘int*’, but argument 2 has type ‘long long int*’ [-Wformat=]
164 | scanf("%d%d",&x,&y);
| ~^ ~~
| | |
| int* long long int*
| %lld
main.cpp:164:23: warning: format ‘%d’ expects argument of type ‘int*’, but argument 3 has type ‘long long int*’ [-Wformat=]
164 | scanf("%d%d",&x,&y);
| ~^ ~~
| | |
| int* long long int*
| %lld
main.cpp:135:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
135 | scanf("%lld",&N);
| ~~~~~^~~~~~~~~~~
main.cpp:136:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
136 | rep(i,N)scanf("%lld",&S[i]);
| ~~~~~^~~~~~~~~~~~~~
main.cpp:137:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
137 | rep(i,N)scanf("%lld",&C[i]);
| ~~~~~^~~~~~~~~~~~~~
main.cpp:141:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
141 | scanf("%lld%lld",&a,&b);
| ~~~~~^~~~~~~~~~~~~~~~~~
main.cpp:148:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
148 | scanf("%lld",&Q);
| ~~~~~^~~~~~~~~~~
main.cp
ソースコード
#include<cstdio>#include<vector>#include<algorithm>#include<iostream>#include<cassert>#define int long longusing namespace std;typedef pair<int,int>pint;typedef vector<int>vint;#define pb push_back#define mp make_pair#define rep(i,n) for(int i=0;i<(n);i++)template<class T,class U>void chmin(T &t,U f){if(t>f)t=f;}template<class T,class U>void chmax(T &t,U f){if(t<f)t=f;}const int mod=1000000007;struct seg_tree{int N;vint dat,sum,lazy;void init(vint &s,vint &c){N=1;while(N<s.size())N<<=1;dat.resize(N*2-1);sum.resize(N*2-1);lazy.resize(N*2-1);rep(i,s.size()){dat[i+N-1]=s[i];sum[i+N-1]=c[i];}for(int i=N-2;i>=0;i--){dat[i]=(dat[i*2+1]+dat[i*2+2])%mod;sum[i]=(sum[i*2+1]+dat[i*2+2])%mod;}}inline void evaluate(int k){dat[k]+=sum[k]*lazy[k]%mod;if(k<N-1){lazy[k*2+1]=(lazy[k*2+1]+lazy[k])%mod;lazy[k*2+2]=(lazy[k*2+2]+lazy[k])%mod;}lazy[k]=0;}void update(int k){dat[k]=(dat[k*2+1]+dat[k*2+2])%mod;}void add(int a,int b,int x){add(a,b,x,0,0,N);}void add(int a,int b,int x,int k,int l,int r){evaluate(k);if(r<=a||b<=l)return;if(a<=l&&r<=b){lazy[k]=(lazy[k]+x+mod)%mod;evaluate(k);return;}add(a,b,x,k*2+1,l,(l+r)/2);add(a,b,x,k*2+2,(l+r)/2,r);update(k);}int get(int a,int b){return get(a,b,0,0,N);}int get(int a,int b,int k,int l,int r){evaluate(k);if(r<=a||b<=l)return 0;if(a<=l&&r<=b)return dat[k];return (get(a,b,k*2+1,l,(l+r)/2)+get(a,b,k*2+2,(l+r)/2,r))%mod;}};const int SIZE=200000;int N,Q;int S[SIZE],C[SIZE];vint G[SIZE];int par[SIZE],depth[SIZE],heavy[SIZE];int head[SIZE],chain[SIZE];vector<seg_tree>seg;int hl_dfs(int v,int p,int d){par[v]=p;depth[v]=d;heavy[v]=-1;int ma=0,sum=0;rep(i,G[v].size()){int to=G[v][i];if(to==p)continue;int val=hl_dfs(to,v,d+1);if(ma<val){ma=val;heavy[v]=to;}sum+=val;}return sum+1;}int hl_init(){hl_dfs(0,-1,0);rep(i,N){if(par[i]>=0&&heavy[par[i]]==i)continue;vint s,c;for(int j=i;~j;j=heavy[j]){head[j]=i;chain[j]=seg.size();s.pb(S[j]);c.pb(C[j]);}seg.pb(seg_tree());seg.back().init(s,c);}}int lca(int u,int v){while(chain[u]!=chain[v]){if(depth[head[u]]<depth[head[v]])swap(u,v);u=par[head[u]];}return depth[u]<depth[v]?u:v;}void add(int v,int x){while(~v){seg[chain[v]].add(0,depth[v]-depth[head[v]]+1,x);v=par[head[v]];}}int get(int v){int ret=0;while(~v){ret+=seg[chain[v]].get(0,depth[v]-depth[head[v]]+1);v=par[head[v]];}return ret;}signed main(){scanf("%lld",&N);rep(i,N)scanf("%lld",&S[i]);rep(i,N)scanf("%lld",&C[i]);rep(i,N-1){int a,b;scanf("%lld%lld",&a,&b);a--;b--;G[a].pb(b);G[b].pb(a);}hl_init();scanf("%lld",&Q);while(Q--){int type;scanf("%lld",&type);if(type==0){int x,y,z;scanf("%lld%lld%lld",&x,&y,&z);x--;y--;int p=lca(x,y);add(x,z);add(y,z);add(p,-z);if(par[p]>=0)add(par[p],-z);}else{int x,y;scanf("%d%d",&x,&y);x--;y--;int p=lca(x,y);int ans=get(x)+get(y)-get(p);if(par[p]>=0)ans-=get(par[p]);ans=(ans+mod*100)%mod;printf("%lld\n",ans);}}return 0;}