結果
問題 | No.898 tri-βutree |
ユーザー |
![]() |
提出日時 | 2019-10-04 22:02:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 196 ms / 4,000 ms |
コード長 | 3,172 bytes |
コンパイル時間 | 2,444 ms |
コンパイル使用メモリ | 215,128 KB |
最終ジャッジ日時 | 2025-01-07 20:32:13 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 21 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:95:31: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 4 has type ‘int64_t*’ {aka ‘long int*’} [-Wformat=] 95 | scanf("%d%d%lld", &u, &v, &w); | ~~~^ ~~ | | | | | int64_t* {aka long int*} | long long int* | %ld main.cpp:120:28: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘int64_t’ {aka ‘long int’} [-Wformat=] 120 | printf("%lld\n", ans); | ~~~^ ~~~ | | | | | int64_t {aka long int} | long long int | %ld main.cpp:89:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 89 | scanf("%d", &N); | ~~~~~^~~~~~~~~~ main.cpp:95:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 95 | scanf("%d%d%lld", &u, &v, &w); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:105:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 105 | scanf("%d", &Q); | ~~~~~^~~~~~~~~~ main.cpp:109:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 109 | scanf("%d%d%d", &x, &y, &z); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>struct Edge {int to;int64_t dist{1};};using EdgeVec = std::vector<Edge>;using EdgeLists = std::vector<EdgeVec>;///////////////////// 木の祖先クエリ /////////////////////// コンストラクタに渡す木は子に向かう有向グラフでも無向グラフでもいい// Edgeは{to}class TreeAncestor {private:using vi = std::vector<int>;using vvi = std::vector<vi>;const EdgeLists& edges_;vvi ancestors_;vi depthList_;const int root_;void initDFS(const int index, const int parent, const int depth){ancestors_[index].front() = parent;depthList_[index] = depth;for (auto& e: edges_[index])if (e.to != parent)initDFS(e.to, index, depth + 1);}public:const vi& depthList;TreeAncestor(const EdgeLists& adjacentList, const int root): edges_(adjacentList), root_(root), depthList(depthList_){int size{1};while (1 << (size - 1) <= (int)edges_.size()) size++;ancestors_.resize(edges_.size(), vi(size));depthList_.resize(edges_.size());initDFS(root_, root_, 0);for (int i{1}; i < size; i++)for (auto& e: ancestors_)e[i] = ancestors_[e[i - 1]][i - 1];}// fromからdistanceだけ根の方向にさかのぼった頂点のindexを返すint calcAncestor(const int from, const int distance) const{int ret{from};for (int digit{}, rest{distance}; rest > 0; rest >>= 1, digit++)if (rest & 1)ret = ancestors_[ret][digit];return ret;}// index0とindex1の最近共通祖先のindexを返すint calcLCA(int index0, int index1) const{if (depthList_[index0] > depthList_[index1])index0 = calcAncestor(index0, depthList_[index0] - depthList_[index1]);elseindex1 = calcAncestor(index1, depthList_[index1] - depthList_[index0]);if (index0 == index1) return index0;for (int digit{(int)ancestors_.front().size() - 1}; digit >= 0; digit--)if (ancestors_[index0][digit] != ancestors_[index1][digit]){index0 = ancestors_[index0][digit];index1 = ancestors_[index1][digit];}return ancestors_[index0][0];}};EdgeLists edges;std::vector<bool> visited;std::vector<int64_t> depth;void dfs(int index);int main(){int N;scanf("%d", &N);edges.resize(N);for (int i{}; i < N - 1; i++){int u, v;int64_t w;scanf("%d%d%lld", &u, &v, &w);edges[u].push_back({v, w});edges[v].push_back({u, w});}TreeAncestor tree(edges, 0);visited.resize(N);depth.resize(N);dfs(0);int Q;scanf("%d", &Q);for (int i{}; i < Q; i++){int x, y, z;scanf("%d%d%d", &x, &y, &z);int lca_xy{tree.calcLCA(x, y)}, lca_xyz{tree.calcLCA(lca_xy, z)};int64_t ans{depth[x] + depth[y] - 2 * depth[lca_xy]};if (lca_xyz == lca_xy){int lca_xz{tree.calcLCA(x, z)}, lca_yz{tree.calcLCA(y, z)};if (lca_yz == lca_xy) ans += depth[z] - depth[lca_xz];else ans += depth[z] - depth[lca_yz];}elseans += depth[z] + depth[lca_xy] - 2 * depth[lca_xyz];printf("%lld\n", ans);}return 0;}void dfs(int index){visited[index] = true;for (auto& e: edges[index]){if (visited[e.to]) continue;depth[e.to] = depth[index] + e.dist;dfs(e.to);}}