結果
問題 | No.386 貪欲な領主 |
ユーザー | haruteru |
提出日時 | 2016-07-07 11:24:41 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 204 ms / 2,000 ms |
コード長 | 1,869 bytes |
コンパイル時間 | 619 ms |
コンパイル使用メモリ | 64,844 KB |
実行使用メモリ | 24,244 KB |
最終ジャッジ日時 | 2024-10-12 23:00:51 |
合計ジャッジ時間 | 3,821 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,760 KB |
testcase_01 | AC | 3 ms
5,760 KB |
testcase_02 | AC | 3 ms
5,760 KB |
testcase_03 | AC | 3 ms
5,760 KB |
testcase_04 | AC | 204 ms
24,148 KB |
testcase_05 | AC | 141 ms
16,676 KB |
testcase_06 | AC | 154 ms
16,588 KB |
testcase_07 | AC | 5 ms
5,760 KB |
testcase_08 | AC | 20 ms
6,528 KB |
testcase_09 | AC | 5 ms
5,760 KB |
testcase_10 | AC | 4 ms
5,760 KB |
testcase_11 | AC | 4 ms
5,760 KB |
testcase_12 | AC | 4 ms
5,760 KB |
testcase_13 | AC | 7 ms
6,016 KB |
testcase_14 | AC | 156 ms
16,596 KB |
testcase_15 | AC | 184 ms
24,244 KB |
ソースコード
#include <iostream> #include <vector> using namespace std; #define MAXN (100000+1) #define MAXM (200000+1) int N, M; vector<int> tree[MAXN]; int cost[MAXN]; int cost_sum[MAXN]; int depth[MAXN]; int log_n; vector<vector<int> > par; void dfs(int v, int p, int c, int d) { par[0][v] = p; depth[v] = d; cost_sum[v] = cost[v] + c; for (int i = 0; i < tree[v].size(); i++) { if (tree[v][i] != p) { dfs(tree[v][i], v, cost_sum[v], d+1); } } } void init() { while (N > (1 << log_n)) log_n++; par = vector<vector<int> >(log_n, vector<int>(N)); dfs(0, -1, 0, 0); for (int k = 0; k < log_n-1; k++) { for(int v = 0; v < N; v++) { if (par[k][v] < 0) { par[k+1][v] = -1; } else { par[k+1][v] = par[k][par[k][v]]; } } } } int solve(int u, int v) { if (depth[u] > depth[v]) { swap(u, v); } for (int k = 0; k < log_n; k++) { if((depth[v] - depth[u]) >> k & 1)v = par[k][v]; } if(u==v)return u; for (int k = log_n-1; k >= 0; k--) { if (par[k][u] != par[k][v]) { u = par[k][u]; v = par[k][v]; } } return par[0][u]; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N; for (int n = 0; n < (N-1); n++) { int a, b; cin >> a; cin >> b; tree[a].push_back(b); tree[b].push_back(a); } for (int n = 0; n < N; n++) { cin >> cost[n]; } init(); unsigned long long total = 0; cin >> M; for (int m = 0; m < M; m++) { int a, b, c, p; cin >> a; cin >> b; cin >> c; p = solve(a, b); total += (cost_sum[a] + cost_sum[b] - (cost_sum[p] * 2) + cost[p]) * c; } cout << total << endl; }