Submission #1310061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310061		Jawad_Akbar_JJ	Harbingers (CEOI09_harbingers)	C++20	30 / 100	171 ms	21516 KiB

harbingers

#include <iostream>
#include <vector>

using namespace std;
#define int long long
const int N = 1<<17, inf = 1e9;
vector<pair<signed, signed>> nei[N];
signed Par[N][17], m[N], cst[N], pre[N], sp[N], start[N];
int c[N], dp[N];

int intersection(int i, int j){
	int k = (c[i] - c[j]) / (m[j] - m[i]);
	if ((c[i] - c[j]) % (m[j] - m[i]) != 0 and c[i] - c[j] > 0)
		k++;
	return k;
}

void dfs(int u, int pr, int id){
	dp[u] = cst[u] + pre[u] * sp[u];
	
	if (id > 0){
		int k = id;
		for (int i=16;i>=0;i--){
			if (Par[k][i] == 0 or start[Par[k][i]] <= sp[u])
				continue;
			k = Par[k][i];
		}
		if (start[k] > sp[u])
			k = Par[k][0];

		dp[u] = min(dp[u], dp[k] + cst[u] + (pre[u] - pre[k]) * sp[u]);

		// cout<<u<<" "<<k<<endl;
	}
	m[u] = inf - pre[u];
	c[u] = dp[u];

	// for (int i=16;i>=0;i--){
	// 	if (Par[id][i] != 0 and intersection(u, Par[id][i]) <= start[Par[id][i]])
	// 		id = Par[Par[id][i]][0];
	// }
	while (id != 0 and intersection(u, id) <= start[id])
		id = Par[id][0];
	if (id)
		start[u] = intersection(u, id);
	Par[u][0] = id;
	for (int i=0;i<16;i++)
		Par[u][i+1] = Par[Par[u][i]][i];

	for (auto [i, w] : nei[u]){
		if (i == pr)
			continue;
		pre[i] = pre[u] + w;
		dfs(i, u, u);
	}
}

signed main(){
	int n;
	cin>>n;

	for (int i=1;i<n;i++){
		int a, b, c;
		cin>>a>>b>>c;
		nei[a].push_back({b, c});
		nei[b].push_back({a, c});
	}

	for (int i=2;i<=n;i++)
		cin>>cst[i]>>sp[i];

	dfs(1, 1, 0);

	for (int i=2;i<=n;i++)
		cout<<dp[i]<<' ';
	cout<<'\n';

	// cout<<Par[4][0]<<endl;
}

• Subtask 1: 30 / 100