結果
問題 | No.386 貪欲な領主 |
ユーザー |
![]() |
提出日時 | 2016-07-04 11:08:37 |
言語 | C++11 (gcc 13.3.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
コンパイルメッセージ
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 200000int n, m, a[V], b[V], u[V], x[Q], y[Q], z[Q];#define NIL 0int list_val[V * 2], list_ptr[V * 2], ptr = NIL + 1, p_f[V], p_l[V];#define ROOT 0int 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;}