結果

問題 No.386 貪欲な領主
ユーザー FF256grhy
提出日時 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]); }
      |                                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0