結果
問題 | No.386 貪欲な領主 |
ユーザー | FF256grhy |
提出日時 | 2016-07-04 11:08:37 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 167 ms / 2,000 ms |
コード長 | 1,936 bytes |
コンパイル時間 | 172 ms |
コンパイル使用メモリ | 24,576 KB |
実行使用メモリ | 21,376 KB |
最終ジャッジ日時 | 2024-10-12 20:05:35 |
合計ジャッジ時間 | 1,801 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 1 ms
5,248 KB |
testcase_04 | AC | 167 ms
21,376 KB |
testcase_05 | AC | 118 ms
20,736 KB |
testcase_06 | AC | 117 ms
20,864 KB |
testcase_07 | AC | 1 ms
5,248 KB |
testcase_08 | AC | 16 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 1 ms
5,248 KB |
testcase_11 | AC | 1 ms
5,248 KB |
testcase_12 | AC | 2 ms
5,248 KB |
testcase_13 | AC | 4 ms
5,248 KB |
testcase_14 | AC | 120 ms
20,864 KB |
testcase_15 | AC | 139 ms
20,864 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:64:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 64 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:65:47: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 65 | for(int i = 0; i < n - 1; i++) { scanf("%d%d" , &a[i], &b[i]); } | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~ main.cpp:66:47: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 66 | for(int i = 0; i < n; i++) { scanf("%d" , &u[i]); } | ~~~~~^~~~~~~~~~~~~~~~~ main.cpp:67:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 67 | scanf("%d", &m); | ~~~~~^~~~~~~~~~ main.cpp:68:47: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 68 | for(int i = 0; i < m; i++) { scanf("%d%d%d", &x[i], &y[i], &z[i]); } | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <stdio.h> #define V 100000 #define Q 200000 int n, m, a[V], b[V], u[V], x[Q], y[Q], z[Q]; #define NIL 0 int list_val[V * 2], list_ptr[V * 2], ptr = NIL + 1, p_f[V], p_l[V]; #define ROOT 0 int height[V], ancestor[V][17], tax[V][17], queue[V], get, set; void add(int p, int v) { list_val[ptr] = v; if(p_l[p] == NIL) { p_f[p] = ptr; } else { list_ptr[ p_l[p] ] = ptr; } p_l[p] = ptr++; return; } int price(int p, int q) { int ans = 0; if(height[p] < height[q]) { int temp = p; p = q; q = temp; } int h = height[p] - height[q]; int i = 0; while(h) { if(h % 2) { ans += tax[p][i]; p = ancestor[p][i]; } i++; h /= 2; } for(i = 16; 0 <= i; i--) { if(ancestor[p][i] != ancestor[q][i]) { ans += tax[p][i] + tax[q][i]; p = ancestor[p][i]; q = ancestor[q][i]; } } if(p == q) { ans += tax[p][0]; } else { ans += tax[p][0] + tax[q][0] + tax[ ancestor[p][0] ][0]; } return ans; } int main() { scanf("%d", &n); for(int i = 0; i < n - 1; i++) { scanf("%d%d" , &a[i], &b[i]); } for(int i = 0; i < n; i++) { scanf("%d" , &u[i]); } scanf("%d", &m); for(int i = 0; i < m; i++) { scanf("%d%d%d", &x[i], &y[i], &z[i]); } for(int i = 0; i < n - 1; i++) { add(a[i], b[i]); add(b[i], a[i]); } //height[ROOT] = 0; //ancestor[ROOT][0] = ROOT; queue[set++] = ROOT; while(get != set) { int p = queue[get++]; tax[p][0] = u[p]; int q = ancestor[p][0], i = 0; while(q != ROOT) { tax[p][i + 1] = tax[p][i] + tax[q][i]; q = ancestor[q][i]; ancestor[p][i + 1] = q; i++; } int r = p_f[p]; while(r != NIL) { int s = list_val[r]; if(height[s] == 0 && s != ROOT) { height[s] = height[p] + 1; ancestor[s][0] = p; queue[set++] = s; } r = list_ptr[r]; } } long long unsigned int ans = 0; for(int i = 0; i < m; i++) { ans += price(x[i], y[i]) * z[i]; } printf("%lld\n", ans); return 0; }