結果
問題 | No.1094 木登り / Climbing tree |
ユーザー | kotatsugame |
提出日時 | 2020-06-24 07:45:22 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 917 ms / 2,000 ms |
コード長 | 922 bytes |
コンパイル時間 | 819 ms |
コンパイル使用メモリ | 72,240 KB |
実行使用メモリ | 49,888 KB |
最終ジャッジ日時 | 2024-04-25 18:25:32 |
合計ジャッジ時間 | 23,370 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 9 ms
29,448 KB |
testcase_01 | AC | 861 ms
38,592 KB |
testcase_02 | AC | 224 ms
49,888 KB |
testcase_03 | AC | 230 ms
30,020 KB |
testcase_04 | AC | 222 ms
33,284 KB |
testcase_05 | AC | 324 ms
37,456 KB |
testcase_06 | AC | 510 ms
32,216 KB |
testcase_07 | AC | 917 ms
38,732 KB |
testcase_08 | AC | 904 ms
38,604 KB |
testcase_09 | AC | 916 ms
38,220 KB |
testcase_10 | AC | 892 ms
38,600 KB |
testcase_11 | AC | 885 ms
38,372 KB |
testcase_12 | AC | 879 ms
38,724 KB |
testcase_13 | AC | 889 ms
38,472 KB |
testcase_14 | AC | 890 ms
38,592 KB |
testcase_15 | AC | 552 ms
34,032 KB |
testcase_16 | AC | 776 ms
45,056 KB |
testcase_17 | AC | 659 ms
39,576 KB |
testcase_18 | AC | 634 ms
36,296 KB |
testcase_19 | AC | 741 ms
42,756 KB |
testcase_20 | AC | 911 ms
38,600 KB |
testcase_21 | AC | 695 ms
40,376 KB |
testcase_22 | AC | 901 ms
38,468 KB |
testcase_23 | AC | 895 ms
38,604 KB |
testcase_24 | AC | 869 ms
38,724 KB |
testcase_25 | AC | 884 ms
38,280 KB |
testcase_26 | AC | 870 ms
38,472 KB |
コンパイルメッセージ
main.cpp:33:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 33 | main() | ^~~~
ソースコード
#include<iostream> #include<vector> using namespace std; int N; vector<pair<int,int> >G[2<<17]; int dep[2<<17],pr[18][2<<17]; long cost[2<<17]; void dfs(int u,int p,int d,int c) { dep[u]=d; cost[u]=c; pr[0][u]=p; for(pair<int,int>e:G[u])if(e.first!=p) { dfs(e.first,u,d+1,c+e.second); } } int lca(int u,int v) { if(dep[u]<dep[v])u^=v^=u^=v; for(int k=0;k<18;k++)if(dep[u]-dep[v]>>k&1) { u=pr[k][u]; } if(u==v)return u; for(int k=18;k--;)if(pr[k][u]!=pr[k][v]) { u=pr[k][u]; v=pr[k][v]; } return pr[0][u]; } main() { cin>>N; for(int i=1;i<N;i++) { int a,b,c;cin>>a>>b>>c; a--,b--; G[a].push_back(make_pair(b,c)); G[b].push_back(make_pair(a,c)); } dfs(0,-1,0,0); for(int k=1;k<18;k++)for(int i=0;i<N;i++) { pr[k][i]=pr[k-1][i]==-1?-1:pr[k-1][pr[k-1][i]]; } int Q;cin>>Q; for(;Q--;) { int u,v;cin>>u>>v; u--,v--; int w=lca(u,v); cout<<cost[u]+cost[v]-cost[w]*2<<endl; } }