結果
問題 | No.386 貪欲な領主 |
ユーザー |
![]() |
提出日時 | 2016-09-16 15:22:38 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 223 ms / 2,000 ms |
コード長 | 1,270 bytes |
コンパイル時間 | 1,562 ms |
コンパイル使用メモリ | 164,452 KB |
実行使用メモリ | 34,688 KB |
最終ジャッジ日時 | 2024-12-23 14:57:00 |
合計ジャッジ時間 | 4,067 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:58:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 58 | scanf("%lld",&n); | ~~~~~^~~~~~~~~~~ main.cpp:62:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 62 | scanf("%lld%lld", &a,&b); | ~~~~~^~~~~~~~~~~~~~~~~~~ main.cpp:68:34: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 68 | for(ll i=0;i<n;i++) scanf("%lld", &U[i]); | ~~~~~^~~~~~~~~~~~~~~ main.cpp:73:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 73 | scanf("%lld",&Q); | ~~~~~^~~~~~~~~~~ main.cpp:77:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 77 | scanf("%lld%lld%lld", &a,&b,&m); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int MAX_N = 100100;const int MAX_LOG= 20;ll n;ll par[MAX_LOG][MAX_N];ll depth[MAX_N];ll cost[MAX_N];vector<vector<ll> > G;vector<ll> U;void dfs(ll v,ll p, ll d, ll c){par[0][v]=p;depth[v]=d;cost[v]=c+U[v];for(auto nxt : G[v]){if(nxt !=p)dfs(nxt, v, d+1, c+U[v]);}}void setPar(){dfs(0,-1,0,0);for(ll i=0;i<MAX_LOG-1;i++){for(ll j=0;j<n;j++){if(par[i][j]== -1)par[i+1][j]= -1;elsepar[i+1][j]=par[i][par[i][j]];}}}ll lca(ll a,ll b){if(depth[a]>depth[b])swap(a,b);for(ll i=0;i<MAX_LOG;i++){if((depth[b]-depth[a]) >> i&1)b=par[i][b];}if(a==b) return a;for(ll i=MAX_LOG-1;i>=0;i--){if(par[i][a]!=par[i][b]){a=par[i][a];b=par[i][b];}}return par[0][a];}int main(){scanf("%lld",&n);G.resize(n);for(ll i=0;i<n-1;i++){ll a,b;scanf("%lld%lld", &a,&b);G[a].push_back(b);G[b].push_back(a);}U.resize(n);for(ll i=0;i<n;i++) scanf("%lld", &U[i]);setPar();ll Q;scanf("%lld",&Q);ll ans=0;for(ll i=0;i<Q;i++){ll a,b,m;scanf("%lld%lld%lld", &a,&b,&m);ll c=lca(a,b);ans+=(cost[a] + cost[b] - 2 * cost[c] + U[c]) * m;}printf("%lld\n", ans);return 0;}