結果

問題 No.386 貪欲な領主
ユーザー FF256grhyFF256grhy
提出日時 2016-07-04 11:08:37
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 133 ms / 2,000 ms
コード長 1,936 bytes
コンパイル時間 237 ms
コンパイル使用メモリ 24,576 KB
実行使用メモリ 21,376 KB
最終ジャッジ日時 2024-04-20 21:50:07
合計ジャッジ時間 1,649 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 0 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 133 ms
21,376 KB
testcase_05 AC 98 ms
20,864 KB
testcase_06 AC 97 ms
20,864 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 15 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 0 ms
5,376 KB
testcase_12 AC 1 ms
5,376 KB
testcase_13 AC 3 ms
5,376 KB
testcase_14 AC 95 ms
20,864 KB
testcase_15 AC 114 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]); }
      |                                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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;
}
0