結果

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