結果
問題 | No.1094 木登り / Climbing tree |
ユーザー | 👑 null |
提出日時 | 2020-06-20 02:02:28 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 428 ms / 2,000 ms |
コード長 | 3,443 bytes |
コンパイル時間 | 965 ms |
コンパイル使用メモリ | 87,976 KB |
実行使用メモリ | 116,648 KB |
最終ジャッジ日時 | 2024-04-25 18:22:27 |
合計ジャッジ時間 | 12,712 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 416 ms
93,440 KB |
testcase_02 | AC | 249 ms
116,648 KB |
testcase_03 | AC | 44 ms
7,552 KB |
testcase_04 | AC | 123 ms
39,792 KB |
testcase_05 | AC | 277 ms
81,356 KB |
testcase_06 | AC | 142 ms
29,676 KB |
testcase_07 | AC | 417 ms
93,512 KB |
testcase_08 | AC | 410 ms
93,372 KB |
testcase_09 | AC | 404 ms
93,296 KB |
testcase_10 | AC | 417 ms
93,316 KB |
testcase_11 | AC | 410 ms
93,316 KB |
testcase_12 | AC | 417 ms
93,236 KB |
testcase_13 | AC | 412 ms
93,336 KB |
testcase_14 | AC | 422 ms
93,184 KB |
testcase_15 | AC | 131 ms
26,896 KB |
testcase_16 | AC | 283 ms
89,516 KB |
testcase_17 | AC | 190 ms
51,624 KB |
testcase_18 | AC | 157 ms
39,348 KB |
testcase_19 | AC | 235 ms
71,220 KB |
testcase_20 | AC | 403 ms
93,352 KB |
testcase_21 | AC | 193 ms
55,356 KB |
testcase_22 | AC | 428 ms
93,320 KB |
testcase_23 | AC | 412 ms
93,332 KB |
testcase_24 | AC | 414 ms
93,408 KB |
testcase_25 | AC | 405 ms
93,408 KB |
testcase_26 | AC | 423 ms
93,352 KB |
ソースコード
#include <cstdio> #include <algorithm> #include <cmath> #include <vector> #define rep(i, n) for(int i = 0; i < (n); ++i) using ll = long long; constexpr int INF = 1073741823; using namespace std; /*----------------------------------------------------------------------------------*/ template<typename T> struct sparsetable { vector<vector<T>> table; vector<int> logtable; vector<int> a; int n; sparsetable(const vector<T> a, int siz) : n(siz), a(a) { logtable.assign(n + 1, 0); for (int i = 2; i <= n; ++i)logtable[i] = logtable[i >> 1] + 1; table.assign(n, vector<T>(logtable[n] + 1, 0)); } sparsetable(initializer_list<T> init) { a = init[0]; n = init[1]; logtable.assign(n + 1, 0); for (int i = 2; i <= n; ++i)logtable[i] = logtable[i >> 1] + 1; table.assign(n, vector<T>(logtable[n] + 1, 0)); } void init(const vector<T> aa, int siz) { a = aa; n = siz; logtable.assign(n + 1, 0); for (int i = 2; i <= n; ++i)logtable[i] = logtable[i >> 1] + 1; table.assign(n, vector<T>(logtable[n] + 1, 0)); } void init() { for (int i = 2; i <= n; ++i)logtable[i] = logtable[i >> 1] + 1; } void build() { for (int k = 0; (1 << k) <= n; ++k) { for (int i = 0; i + (1 << k) <= n; ++i) { if (k) table[i][k] = (a[table[i][k - 1]] < a[table[i + (1 << (k - 1))][k - 1]] ? table[i][k - 1] : table[i + (1 << (k - 1))][k - 1]); else table[i][k] = i; } } } //[l, r) RMQ int query(int l, int r) { int k = logtable[r - l]; return (a[table[l][k]] < a[table[r - (1 << k)][k]] ? table[l][k] : table[r - (1 << k)][k]); } }; void eulertour(const int& now, const int& bef, int& cnt, const vector<vector<pair<int, int>>>& graph, const int& d, vector<int>& vs, vector<int>& depth, vector<int>& id) { depth.emplace_back(d); vs.emplace_back(now); id[now] = min(id[now], cnt); for (const auto& aa : graph[now]) { if (aa.first != bef) { ++cnt; eulertour(aa.first, now, cnt, graph, d + aa.second, vs, depth, id); ++cnt; depth.emplace_back(d); vs.emplace_back(now); } } } struct LCA { vector<int> vs, depth, id, tmp = { 0 }; vector<vector<pair<int, int>>> tree; sparsetable<int> table{ tmp, 0 }; int n, root; LCA(vector<vector<pair<int, int>>> tree, int n, int root) : tree(tree), n(n), root(root) { id.assign(n, INF); int cnt = 0, d = 0; eulertour(root, -1, cnt, tree, d, vs, depth, id); table.init(depth, depth.size()); table.build(); } int query(int l, int r) { if (id[l] > id[r])swap(l, r); return vs[table.query(id[l], id[r] + 1)]; } int depthq(int n) { return depth[id[n]]; } }; int main() { int n; scanf("%d", &n); vector<vector<pair<int, int>>> g(n); rep(i, n - 1) { int a, b, c; scanf("%d%d%d", &a, &b, &c); --a, --b; g[a].emplace_back(b, c); g[b].emplace_back(a, c); } LCA lca(g, n, 0); int q; scanf("%d", &q); while (q--) { int s, t; scanf("%d%d", &s, &t); --s, --t; printf("%d\n", lca.depthq(s) + lca.depthq(t) - 2 * lca.depthq(lca.query(s, t))); } return 0; }