結果
問題 | No.386 貪欲な領主 |
ユーザー | haruteru |
提出日時 | 2016-07-06 13:45:33 |
言語 | C++11 (gcc 11.4.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,236 bytes |
コンパイル時間 | 527 ms |
コンパイル使用メモリ | 62,332 KB |
実行使用メモリ | 23,136 KB |
最終ジャッジ日時 | 2024-10-12 20:25:54 |
合計ジャッジ時間 | 4,203 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
13,636 KB |
testcase_01 | AC | 3 ms
6,820 KB |
testcase_02 | AC | 3 ms
6,856 KB |
testcase_03 | AC | 3 ms
6,820 KB |
testcase_04 | TLE | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
ソースコード
#include <iostream> #include <vector> using namespace std; typedef unsigned long long ULL; #define MAXN (100000+1) #define MAXM (200000+1) ULL N, M, A, B, C, TOTAL; vector<int> tree[MAXN]; ULL cost[MAXN]; pair<int,int> lca[MAXN]; void build(int n, int p, int depth) { lca[n] = make_pair(p, depth); for (int i = 0; i < tree[n].size(); i++) { if (tree[n][i] != p) { build(tree[n][i], n, depth+1); } } } ULL solve(int a, int b) { ULL aa = 0; ULL bb = 0; while (1) { if (a == b) { return aa + bb + cost[a]; } else if (lca[a].second > lca[b].second) { aa += cost[a]; a = lca[a].first; } else { bb += cost[b]; b = lca[b].first; } } return 0; } int main() { cin >> N; for (int n = 0; n < (N-1); n++) { cin >> A; cin >> B; tree[A].push_back(B); tree[B].push_back(A); } for (int n = 0; n < N; n++) { cin >> cost[n]; } build(0, -1, 0); cin >> M; for (int m = 0; m < M; m++) { cin >> A; cin >> B; cin >> C; TOTAL += solve(A, B) * C; } cout << TOTAL << endl; }