結果
問題 | No.1094 木登り / Climbing tree |
ユーザー | onsen_manjuuu |
提出日時 | 2020-06-25 01:14:17 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,050 ms / 2,000 ms |
コード長 | 2,465 bytes |
コンパイル時間 | 1,987 ms |
コンパイル使用メモリ | 181,072 KB |
実行使用メモリ | 66,384 KB |
最終ジャッジ日時 | 2024-04-25 18:26:55 |
合計ジャッジ時間 | 25,483 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 969 ms
60,920 KB |
testcase_02 | AC | 313 ms
66,384 KB |
testcase_03 | AC | 215 ms
6,940 KB |
testcase_04 | AC | 236 ms
28,288 KB |
testcase_05 | AC | 393 ms
53,196 KB |
testcase_06 | AC | 514 ms
21,248 KB |
testcase_07 | AC | 986 ms
60,776 KB |
testcase_08 | AC | 958 ms
60,920 KB |
testcase_09 | AC | 961 ms
60,988 KB |
testcase_10 | AC | 1,027 ms
60,952 KB |
testcase_11 | AC | 966 ms
60,916 KB |
testcase_12 | AC | 997 ms
60,988 KB |
testcase_13 | AC | 1,050 ms
60,912 KB |
testcase_14 | AC | 1,017 ms
60,928 KB |
testcase_15 | AC | 517 ms
17,152 KB |
testcase_16 | AC | 847 ms
51,196 KB |
testcase_17 | AC | 676 ms
31,744 KB |
testcase_18 | AC | 612 ms
24,576 KB |
testcase_19 | AC | 775 ms
43,560 KB |
testcase_20 | AC | 1,032 ms
60,924 KB |
testcase_21 | AC | 669 ms
33,768 KB |
testcase_22 | AC | 957 ms
60,956 KB |
testcase_23 | AC | 959 ms
60,840 KB |
testcase_24 | AC | 900 ms
60,924 KB |
testcase_25 | AC | 916 ms
60,904 KB |
testcase_26 | AC | 928 ms
61,036 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; for(int i = D; i >= 0; i--) { if(par[u][i] != par[v][i]) { u = par[u][i]; v = par[v][i]; } } return par[u][0]; } //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; } }