結果
問題 | No.1094 木登り / Climbing tree |
ユーザー | onsen_manjuuu |
提出日時 | 2020-06-24 03:18:46 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,760 ms / 2,000 ms |
コード長 | 2,464 bytes |
コンパイル時間 | 2,623 ms |
コンパイル使用メモリ | 182,332 KB |
実行使用メモリ | 66,108 KB |
最終ジャッジ日時 | 2023-10-13 00:32:27 |
合計ジャッジ時間 | 39,462 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 1,636 ms
60,556 KB |
testcase_02 | AC | 308 ms
66,108 KB |
testcase_03 | AC | 347 ms
5,940 KB |
testcase_04 | AC | 345 ms
28,128 KB |
testcase_05 | AC | 528 ms
53,040 KB |
testcase_06 | AC | 858 ms
21,036 KB |
testcase_07 | AC | 1,749 ms
60,504 KB |
testcase_08 | AC | 1,727 ms
60,688 KB |
testcase_09 | AC | 1,686 ms
60,592 KB |
testcase_10 | AC | 1,701 ms
60,576 KB |
testcase_11 | AC | 1,696 ms
60,588 KB |
testcase_12 | AC | 1,692 ms
60,504 KB |
testcase_13 | AC | 1,662 ms
60,504 KB |
testcase_14 | AC | 1,690 ms
60,648 KB |
testcase_15 | AC | 626 ms
17,020 KB |
testcase_16 | AC | 922 ms
51,316 KB |
testcase_17 | AC | 741 ms
31,604 KB |
testcase_18 | AC | 697 ms
24,500 KB |
testcase_19 | AC | 884 ms
43,108 KB |
testcase_20 | AC | 1,760 ms
60,560 KB |
testcase_21 | AC | 784 ms
33,656 KB |
testcase_22 | AC | 1,742 ms
60,512 KB |
testcase_23 | AC | 1,691 ms
60,656 KB |
testcase_24 | AC | 1,727 ms
60,556 KB |
testcase_25 | AC | 1,652 ms
60,580 KB |
testcase_26 | AC | 1,660 ms
60,864 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; //constructor: LCA(graph); template<class T> class LCA_weight { private: int n; int D = 30; //hight vector<int> depth; //depth from root vector<vector<pair<int,T>>> hen; //tree vector<vector<int>> par; //doubling array vector<T> dista; //distance form root void dfs(int v, int p, int dep, T dep_dist) { par[v][0] = p; depth[v] = dep; dista[v] = dep_dist; for(auto i : hen[v]) { if(i.first == p)continue; dfs(i.first, v, dep + 1, dep_dist + i.second); } } public: LCA_weight(const vector<vector<pair<int,T>>>& hen):hen(hen) { n = hen.size(); par.resize(n, vector<int>(D + 1)); depth.resize(n); dista.resize(n); dfs(0, -1, 0, 0); for(int i = 0; i < D; i++) { for(int j = 0; j < n; j++) { if(par[j][i] == -1)par[j][i + 1] = -1; else par[j][i + 1] = par[par[j][i]][i]; } } } //go back to root int back(int v, int dist) { for(int i = 0; i < D; i++)if((1 << i) & dist) { if(v == -1)return v; v = par[v][i]; } return v; } //get LCA int get(int u, int v) { int ret = 0; if(depth[u] > depth[v])swap(u, v); ret = depth[v] - depth[u]; v = back(v, ret); if(u == v)return v; int lef = 0, rig = n; while(rig - lef > 1) { int mid = (rig + lef) / 2; (back(u, mid) == back(v, mid) ? rig : lef) = mid; } return back(v, rig); } //u-v path distance T dist(int u, int v) { int lca = get(u, v); return (dista[u] + dista[v]) - dista[lca] * 2; } //print parents void print(int i) { cerr << "["; for(int j = 0; j < n; j++)cerr << par[j][i] << (j == n - 1 ? "" : ","); cerr << "]"; } }; int main() { int n; cin >> n; vector<vector<pair<int,int>>> hen(n); for(int i = 0; i < n - 1; i++) { int a, b, c; cin >> a >> b >> c; a--, b--; hen[a].emplace_back(b, c); hen[b].emplace_back(a, c); } LCA_weight<int> tree(hen); int q; cin >> q; while(q--) { int s, t; cin >> s >> t; cout << tree.dist(s - 1, t - 1) << endl; } }