Submission #927912

#	Time	Username	Problem	Language	Result	Execution time	Memory
927912		TAhmed33	Harbingers (CEOI09_harbingers)	C++98	100 / 100	82 ms	20116 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
typedef long long ll;
typedef long double ld;
const int MAXN = 1e5 + 25;
vector <pair <int, int>> adj[MAXN];
ll dep[MAXN];
ll val[MAXN], start[MAXN], dp[MAXN];
void calc (int pos, int par) {
	for (auto j : adj[pos]) {
		if (j.first == par) continue;
		dep[j.first] = j.second + dep[pos];
		calc(j.first, pos);
	}
}
pair <ll, ll> hull[MAXN];
ld inter (pair <ll, ll> a, pair <ll, ll> b) {
	return 1.0 * (a.second - b.second) / (b.first - a.first);
}
int sze = 0;
ll get (ll x) {
	if (sze == 1) {
		return hull[0].first * x + hull[0].second;
	}
	if (inter(hull[sze - 1], hull[sze - 2]) + 1e-9 < x) {
		return hull[sze - 1].first * x + hull[sze - 1].second;
	}
	int l = 0, r = sze - 2, ans = sze - 1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (inter(hull[mid], hull[mid + 1]) > x + 1e-9) {
			r = mid - 1; ans = mid;
		} else {
			l = mid + 1;
		}
	}
	return hull[ans].first * x + hull[ans].second;
}
void dfs (int pos, int par) {
	int prev_sze = sze;
	if (par != -1) dp[pos] = start[pos] + dep[pos] * val[pos] + get(val[pos]);
	pair <ll, ll> line = {-dep[pos], dp[pos]};
	int l = 1, r = sze - 1, ans = sze;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (inter(hull[mid], hull[mid - 1]) > inter(line, hull[mid]) + 1e-9) {
			r = mid - 1; ans = mid;
		} else {
			l = mid + 1;
		}
	}
	sze = ans + 1; pair <ll, ll> pp = hull[sze - 1]; hull[sze - 1] = line; 
	for (auto j : adj[pos]) if (j.first != par) dfs(j.first, pos);
	hull[sze - 1] = pp; sze = prev_sze;
}
int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 1; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}
	for (int i = 2; i <= n; i++) cin >> start[i] >> val[i];
	calc(1, -1);
	dfs(1, -1);
	for (int i = 2; i <= n; i++) cout << dp[i] << " ";
}

• Subtask 1: 100 / 100