結果

問題 No.898 tri-βutree
ユーザー niuezniuez
提出日時 2019-09-16 21:32:36
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 548 ms / 4,000 ms
コード長 2,431 bytes
コンパイル時間 2,082 ms
コンパイル使用メモリ 185,028 KB
実行使用メモリ 95,124 KB
最終ジャッジ日時 2024-11-08 21:38:25
合計ジャッジ時間 12,982 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 1
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()
#define let auto const
struct eulartour_subtree {
vector<vector<pair<i64, i64>>> G;
vector<i64> tour;
vector<i64> L, R;
vector<i64> depth;
vector<i64> weight;
eulartour_subtree(i64 n): G(n), L(n), R(n), depth(n), weight(n) {}
void add_edge(i64 u, i64 v, i64 w) {
G[u].push_back({v, w});
G[v].push_back({u, w});
}
void dfs(i64 v, i64 f, i64 d, i64 w) {
tour.push_back(v);
L[v] = tour.size() - 1;
depth[v] = d;
weight[v] = w;
for(auto to: G[v]) {
if(to.first == f) continue;
dfs(to.first, v, d + 1, w + to.second);
tour.push_back(v);
}
R[v] = tour.size() - 1;
}
i64 start_tour(i64 r) {
dfs(r, -1, 0, 0);
return tour.size();
}
};
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct sparse_table {
using Band = pair<i64, i64>;
Band ope(const Band& a, const Band b) { return min(a, b); }
i64 N;
vector<Band> A;
vector<i64> log_t;
vector<vector<Band>> table;
sparse_table(vector<Band> arr) : N(arr.size()), A(arr), log_t(arr.size() + 1) {
for(int i = 2;i < N + 1;i++) {
log_t[i] = log_t[i >> 1] + 1;
}
table.resize(N, vector<Band>(log_t[N] + 1));
for(int i = 0;i < N;i++) {
table[i][0] = arr[i];
}
for(int k = 1;(1 << k) <= N;k++) {
for(int i = 0;i + (1 << k) <= N;i++) {
table[i][k] = ope(table[i][k - 1], table[i + (1 << (k - 1))][k - 1]);
}
}
}
/* [s, t] */
Band query(i64 s, i64 t) {
i64 k = log_t[t - s + 1];
return ope(table[s][k], table[t - (1 << k) + 1][k]);
}
};
int main() {
i64 N;
cin >> N;
eulartour_subtree eul(N);
for(int i = 0;i < N - 1;i++) {
i64 a, b, c;
cin >> a >> b >> c;
eul.add_edge(a, b, c);
}
i64 sz = eul.start_tour(0);
vector<pair<i64, i64>> arr(sz);
for(i64 i = 0;i < sz;i++) {
arr[i] = { eul.depth[eul.tour[i]], eul.tour[i] };
}
sparse_table spa(arr);
auto dist = [&](i64 a, i64 b) -> i64 {
i64 c = spa.query(min(eul.L[a], eul.L[b]), max(eul.R[a], eul.R[b])).second;
return eul.weight[a] + eul.weight[b] - 2 * eul.weight[c];
};
i64 Q;
cin >> Q;
for(i64 q = 0; q < Q; q++) {
i64 x, y, z;
cin >> x >> y >> z;
cout << (dist(x, y) + dist(y, z) + dist(x, z)) / 2 << endl;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0