結果
問題 | No.898 tri-βutree |
ユーザー | btk |
提出日時 | 2019-10-04 22:37:48 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 720 ms / 4,000 ms |
コード長 | 13,142 bytes |
コンパイル時間 | 2,386 ms |
コンパイル使用メモリ | 212,464 KB |
実行使用メモリ | 26,752 KB |
最終ジャッジ日時 | 2024-11-08 22:20:28 |
合計ジャッジ時間 | 15,371 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 479 ms
26,752 KB |
testcase_01 | AC | 2 ms
5,248 KB |
testcase_02 | AC | 3 ms
5,248 KB |
testcase_03 | AC | 3 ms
5,248 KB |
testcase_04 | AC | 3 ms
5,248 KB |
testcase_05 | AC | 3 ms
5,248 KB |
testcase_06 | AC | 3 ms
5,248 KB |
testcase_07 | AC | 663 ms
14,720 KB |
testcase_08 | AC | 720 ms
14,848 KB |
testcase_09 | AC | 654 ms
14,720 KB |
testcase_10 | AC | 681 ms
14,848 KB |
testcase_11 | AC | 668 ms
14,848 KB |
testcase_12 | AC | 667 ms
14,848 KB |
testcase_13 | AC | 668 ms
14,848 KB |
testcase_14 | AC | 676 ms
14,720 KB |
testcase_15 | AC | 664 ms
14,848 KB |
testcase_16 | AC | 662 ms
14,848 KB |
testcase_17 | AC | 678 ms
14,848 KB |
testcase_18 | AC | 666 ms
14,720 KB |
testcase_19 | AC | 681 ms
14,720 KB |
testcase_20 | AC | 663 ms
14,848 KB |
testcase_21 | AC | 670 ms
14,720 KB |
コンパイルメッセージ
main.cpp:34:13: warning: #pragma once in main file 34 | # pragma once | ^~~~
ソースコード
// https://yukicoder.me/problems/no/898 #define CIN_ONLY #define DECIMAL_DIGITS 10 #define STATIC_MOD 1e9 + 7 #ifdef BTK /*<head>*/ # include "Template.hpp" /*</head>*/ #else /*<body>*/ /* #region auto includes */ /* #region stl */ /*<stl>*/ # include <bits/stdc++.h> # include <sys/types.h> # include <unistd.h> using namespace std; /*</stl>*/ /* #endregion */ /* #region template/IncludeSTL.hpp*/ /** * @file IncludeSTL.hpp * @author btk * @brief 標準ライブラリをincludeするだけ * @version 0.1 * @date 2019-07-21 * * @copyright Copyright (c) 2019 * */ /*<head>*/ # pragma once /*</head>*/ /*<stl>*/ # include <bits/stdc++.h> # include <sys/types.h> # include <unistd.h> using namespace std; /*</stl>*/ /* #endregion */ /* #region template/Macro.hpp*/ /** * @file Macro.hpp * @author btk * @brief マクロとか,LLとか * @version 0.1 * @date 2019-07-13 * * @copyright Copyright (c) 2019 * */ //! LL using LL = long long; /** * @def DEBUG * @brief デバッグ用のif文 提出時はif(0)で実行されない */ /*</head>*/ # ifdef BTK # define DEBUG if (1) # else # ifdef CIN_ONLY # define FAST_IO # endif # define DEBUG if (0) # endif /** * @def ALL(v) * @brief * ALLマクロ */ # define ALL(v) (v).begin(), (v).end() /** * @def REC(ret, ...) * @brief * 再帰ラムダをするためのマクロ */ # define REC(ret, ...) std::function<ret(__VA_ARGS__)> /** * @def VAR_NAME(var) * @brief 変数名を取得する */ # define VAR_NAME(var) # var /** * @brief * rangeで生まれる使わない変数を消す用(警告消し) */ template <typename T> inline T& unused_var(T& v) { return v; } /* #endregion */ /* #region template/IO.hpp*/ /** * @file IO.hpp * @author btk * @brief cin高速化とか,出力の小数桁固定とか * @version 0.1 * @date 2019-07-13 * * @copyright Copyright (c) 2019 */ /** * @brief 入出力の設定を行うための構造体 */ struct cww { /** * @brief Construct a new cww::cww object * @details * CIN_ONLYを定義すると,submit時にcinとscanfの同期を切る設定が走る * DECIMAL_DIGITSを定義すると,doubleの出力時指定した桁数分小数部を吐くようになる */ cww() { # ifdef FAST_IO ios::sync_with_stdio(false); cin.tie(0); # endif # ifdef DECIMAL_DIGITS cout << fixed; cout << setprecision(DECIMAL_DIGITS); # endif } }; //! 入出力設定構造体を実体化 cww star; /** * @brief * vectorに直接cin流すためのやつ * @tparam T * @param is * @param v * @return istream& */ template <typename T> std::istream& operator>>(std::istream& is, std::vector<T>& v) { for (auto& it : v) is >> it; return is; } /* #endregion */ /* #region template/Loop.hpp*/ /** * @file Loop.hpp * @author btk * @brief rangeとかループ系のクラス * @version 0.1 * @date 2019-07-13 * * @copyright Copyright (c) 2019 * */ /** * @brief * rangeを逆向きに操作したいとき用 * @details * ループの範囲は[bg,ed)なので注意 * @see range */ class reverse_range { private: struct I { int x; int operator*() { return x - 1; } bool operator!=(I& lhs) { return x > lhs.x; } void operator++() { --x; } }; I i, n; public: /** * @brief Construct a new reverse range object * * @param n */ reverse_range(int n) : i({0}), n({n}) {} /** * @brief Construct a new reverse range object * * @param i * @param n */ reverse_range(int i, int n) : i({i}), n({n}) {} /** * @brief * begin iterator * @return I& */ I& begin() { return n; } /** * @brief * end iterator * @return I& */ I& end() { return i; } }; /** * @brief * python みたいな range-based for を実現 * @details * ループの範囲は[bg,ed)なので注意 * !つけると逆向きにループが回る (reverse_range) * 空間計算量はO(1) * 使わない変数ができて警告が出がちなので,unused_varとかを使って警告消しするとよい */ class range { private: struct I { int x; int operator*() { return x; } bool operator!=(I& lhs) { return x < lhs.x; } void operator++() { ++x; } }; I i, n; public: /** * @brief Construct a new range object * * @param n */ range(int n) : i({0}), n({n}) {} /** * @brief Construct a new range object * * @param i * @param n */ range(int i, int n) : i({i}), n({n}) {} /** * @brief * begin iterator * @return I& */ I& begin() { return i; } /** * @brief * end iterator * @return I& */ I& end() { return n; } /** * @brief * 逆向きに参照するrange(reverse_rangeを取得できるs) * @return reverse_range */ reverse_range operator!() { return reverse_range(*i, *n); } }; /* #endregion */ /* #region template/MinMaxOperation.hpp*/ /** * @file MinMaxOperation.hpp * @author btk * @brief 最大値とか最小値を求める * @version 0.1 * @date 2019-07-04 * * @copyright Copyright (c) 2019 * */ /** * @brief 2項の最小値求める * * @tparam T */ template <typename T> struct min_op { /** * @brief 本体 * * @param l * @param r * @return T */ static T exec(const T l, const T r) { return l < r ? l : r; } }; /** * @brief 2項の最大値求める * * @tparam T */ template <typename T> struct max_op { /** * @brief 本体 * * @param l * @param r * @return T */ static T exec(const T l, const T r) { return l > r ? l : r; } }; /** * @brief テンプレート再帰の末尾 * * @tparam F 二項演算 * @tparam T * @param v * @return T */ template <typename F, typename T> inline T multi_op(T&& v) { return v; } /** * @brief 複数項における演算の結果を返す * * @tparam F * @tparam T * @tparam Ts * @param head * @param tail * @return T */ template <typename F, typename T, typename... Ts> inline T multi_op(const T head, Ts&&... tail) { return F::exec(head, multi_op<F>(tail...)); } /** * @brief 複数項の最小値 * @see multi_op * @tparam T * @tparam Ts * @param head * @param tail * @return T */ template <typename T, typename... Ts> inline T multi_min(T&& head, Ts&&... tail) { return multi_op<min_op<T>>(head, tail...); } /** * @brief 複数項の最大値 * @see multi_op * @tparam T * @tparam Ts * @param head * @param tail * @return T */ template <typename T, typename... Ts> inline T multi_max(T&& head, Ts&&... tail) { return multi_op<max_op<T>>(head, tail...); } /** * @brief * 先頭の値をFで参照する関数に基づいて変更できたらする * @tparam F * @tparam T * @tparam Ts * @param target * @param candidates * @return true * @return false */ template <typename F, typename T, typename... Ts> inline bool ch_op(T& target, Ts&&... candidates) { const T old = target; target = multi_op<F>(target, candidates...); return old != target; } /** * @brief change min * @tparam T 型 * @param target 変更する値 * @param candidates * @return 更新があればtrue */ template <typename T, typename... Ts> inline bool chmin(T& target, Ts&&... candidates) { return ch_op<min_op<T>>(target, candidates...); } /** * @brief chminのmax版 * @see chmin * @tparam T 型 * @param target 変更する値 * @param candidates * @return 更新があればtrue */ template <typename T, typename... Ts> inline bool chmax(T& target, Ts&&... candidates) { return ch_op<max_op<T>>(target, candidates...); } /* #endregion */ /* #region template/Random.hpp*/ /** * @file Random.hpp * @author btk * @brief 乱数生成系 * @version 0.1 * @date 2019-07-13 * @copyright Copyright (c) 2019 */ //! 乱数のシード値をプロセスIDとして取得 const pid_t pid = getpid(); /** * @brief XorShift32の実装 */ class XorShift32 { private: //! XorShiftの現在の値 unsigned value; /** * @brief XorShift32のアルゴリズムに基づいて value を更新 */ inline void update() { value = value ^ (value << 13); value = value ^ (value >> 17); value = value ^ (value << 5); } /** * @brief 値を更新し,更新前の値を返却 * @return unsigned 呼び出し時の value を用いる */ inline unsigned get() { unsigned v = value; update(); return v; } public: /** * @brief [0, 2^bit) の範囲の乱数値を取り出す * @tparam デフォルトは31 * @return int */ template <int bit = 31> inline int next_int() { return (int)(get() >> (32 - bit)); } /** * @brief [-2^bit,2^bit)の範囲の乱数値を取り出す * @tparam デフォルトは31 * @return int */ template <int bit = 31> inline int next_signed() { unsigned v = get(); return (int)((v >> (31 - bit)) - (1 << (bit))); } /** * @brief next_int呼び出し時の最大値を取得 * @tparam 31 * @return int */ template <int bit = 31> inline int range_max() { return (int)((1u << bit) - 1); }; /** * @brief Construct a new XorShift32 object * @param seed * @details 初期シードをvalueとするXorShift32のインスタンスを生成 */ XorShift32(const unsigned seed) { value = seed; update(); } /** * @brief Construct a new XorShift 32 object * @details 初期シードをプロセスIDとするXorShift32のインスタンスを生成 */ XorShift32() : XorShift32(pid) {} }; /* #endregion */ /* #region Template.hpp*/ /** * @file Template.hpp * @brief 競技プログラミング用テンプレート * @author btk15049 * @date 2019/05/02 */ /* #endregion */ /* #endregion */ /*</body>*/ #endif typedef vector<int> V; typedef vector<V> Graph; int a[112345]; int b[112345]; LL c[112345]; namespace LCA { /* use doubling - build : O(nlogn) - query : O(logn) */ constexpr int BUF = 112345; constexpr int LOG = 20; // LOG >= log(BUF) int pp[LOG][BUF]; int *p = pp[0]; int depth[BUF]; // cost[v]=根からvまでの距離 LL cost[BUF]; void dfs(int v, int q, Graph &g) { for (int e : g[v]) { int u = v ^ a[e] ^ b[e]; if (u == q) continue; depth[u] = depth[v] + 1; cost[u] = cost[v] + c[e]; p[u] = v; dfs(u, v, g); } } // lca void build(Graph &g, int root = 0) { int n = g.size(); for (int i = 0; i < n; i++) { pp[0][i] = -1; } depth[root] = 0; dfs(root, root, g); for (int k = 0, f = 1; f; k++) { f = 0; for (int i = 0; i < n; i++) { if (pp[k][i] < 0) pp[k + 1][i] = -1; else { pp[k + 1][i] = pp[k][pp[k][i]]; f = 1; } } } } inline int lca(int u, int v) { if (depth[u] > depth[v]) swap(u, v); for (int k = 0, d; (d = depth[v] - depth[u]); k++) { if ((d >> k) & 1) { v = pp[k][v]; } } if (u == v) return v; for (int k = LOG - 1; k >= 0; k--) { if (pp[k][u] != pp[k][v]) { u = pp[k][u]; v = pp[k][v]; } } return pp[0][u]; } inline int dist(int a, int b) { int c = lca(a, b); return depth[a] + depth[b] - 2 * depth[c]; } inline LL sa(int a, int b) { int c = lca(a, b); return cost[a] + cost[b] - 2 * cost[c]; } inline int lca(int a, int b, int c) { int d = lca(a, b); int e = lca(b, c); int f = lca(c, a); int dd = dist(d, a) + dist(d, b) + dist(d, c); int ee = dist(e, a) + dist(e, b) + dist(e, c); int ff = dist(f, a) + dist(f, b) + dist(f, c); vector<pair<int, int>> v = {{dd, d}, {ee, e}, {ff, f}}; return min_element(v.begin(), v.end())->second; } } // namespace LCA int main() { /* write here */ int N; cin >> N; Graph g(N); for (int i : range(N - 1)) { cin >> a[i] >> b[i] >> c[i]; g[a[i]].push_back(i); g[b[i]].push_back(i); } LCA::build(g); int Q; cin >> Q; for (int i : range(Q)) { int x, y, z; cin >> x >> y >> z; int p = LCA::lca(x, y, z); cerr << p << endl; cout << LCA::sa(p, x) + LCA::sa(p, y) + LCA::sa(p, z) << endl; } return 0; }