結果
問題 | No.898 tri-βutree |
ユーザー | fine |
提出日時 | 2019-10-04 21:59:31 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 179 ms / 4,000 ms |
コード長 | 2,256 bytes |
コンパイル時間 | 1,939 ms |
コンパイル使用メモリ | 170,008 KB |
実行使用メモリ | 26,196 KB |
最終ジャッジ日時 | 2023-08-08 15:56:46 |
合計ジャッジ時間 | 7,064 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 79 ms
26,196 KB |
testcase_01 | AC | 4 ms
11,516 KB |
testcase_02 | AC | 4 ms
11,544 KB |
testcase_03 | AC | 4 ms
11,592 KB |
testcase_04 | AC | 4 ms
11,708 KB |
testcase_05 | AC | 4 ms
11,616 KB |
testcase_06 | AC | 4 ms
11,488 KB |
testcase_07 | AC | 177 ms
18,672 KB |
testcase_08 | AC | 173 ms
18,740 KB |
testcase_09 | AC | 170 ms
18,764 KB |
testcase_10 | AC | 170 ms
18,616 KB |
testcase_11 | AC | 176 ms
18,936 KB |
testcase_12 | AC | 179 ms
18,612 KB |
testcase_13 | AC | 175 ms
18,692 KB |
testcase_14 | AC | 172 ms
18,636 KB |
testcase_15 | AC | 173 ms
18,616 KB |
testcase_16 | AC | 170 ms
18,720 KB |
testcase_17 | AC | 173 ms
18,616 KB |
testcase_18 | AC | 172 ms
18,624 KB |
testcase_19 | AC | 172 ms
18,620 KB |
testcase_20 | AC | 175 ms
18,632 KB |
testcase_21 | AC | 178 ms
18,612 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using P = pair<int, ll>; const int MAX_V = 100000; const int MAX_LOG_V = 17; vector<P> G[MAX_V]; int root = 0; int parent[MAX_LOG_V][MAX_V]; int depth[MAX_V]; ll weights[MAX_V]; void dfs(int v, int p, int d, ll w) { parent[0][v] = p; depth[v] = d; weights[v] = w; for (int i = 0; i < G[v].size(); i++) { if (G[v][i].first != p) dfs(G[v][i].first, v, d + 1, w + G[v][i].second); } } void init(int V) { dfs(root, -1, 0, 0); for (int k = 0; k + 1 < MAX_LOG_V; k++) { for (int v = 0; v < V; v++) { if (parent[k][v] < 0) parent[k + 1][v] = -1; else parent[k + 1][v] = parent[k][parent[k][v]]; } } } int lca(int u, int v) { if (depth[u] > depth[v]) swap(u, v); for (int k = 0; k < MAX_LOG_V; k++) { if ((depth[v] - depth[u]) >> k & 1) { v = parent[k][v]; } } if (u == v) return u; for (int k = MAX_LOG_V - 1; k >= 0; k--) { if (parent[k][u] != parent[k][v]) { u = parent[k][u]; v = parent[k][v]; } } return parent[0][u]; } int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; for (int i = 1; i < n; i++) { int u, v; ll w; cin >> u >> v >> w; G[u].emplace_back(v, w); G[v].emplace_back(u, w); } init(n); int q; cin >> q; for (int i = 0; i < q; i++) { int x, y, z; cin >> x >> y >> z; int xy = lca(x, y); int yz = lca(y, z); int zx = lca(z, x); int tar = xy; int hoge = lca(xy, z); ll ans = weights[x] + weights[y] - weights[xy] * 2; ans += weights[z] + weights[xy] - weights[hoge] * 2; if (depth[tar] < depth[yz]) { tar = yz; ans = weights[y] + weights[z] - weights[yz] * 2; ans += weights[x] + weights[yz] - weights[hoge] * 2; } if (depth[tar] < depth[zx]) { tar = zx; ans = weights[z] + weights[x] - weights[zx] * 2; ans += weights[y] + weights[zx] - weights[hoge] * 2; } cout << ans << "\n"; } return 0; }