Submission #849275

#	Time	Username	Problem	Language	Result	Execution time	Memory
849275		IBory	Harbingers (CEOI09_harbingers)	C++17	30 / 100	115 ms	65536 KiB

harbingers

#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;

const ll MAX = 100007, INF = 2E18 + 9, xL = -1E9 - 7, xR = 1E9 + 7;
ll A[MAX], B[MAX], X[MAX], dp[MAX];
vector<pii> G[MAX];

struct LiChao {
	struct Line {
		ll a, b;
		ll Get(ll x) { return a * x + b; }
	};
	struct Node {
		int L, R;
		ll sL, sR;
		Line line;
	};
	vector<Node> tree;
	vector<pair<int, Node>> rev;
	LiChao() { tree.push_back({ -1, -1, xL, xR, { 0, INF } }); }
	void Update(int n, Line v) {
		ll sL = tree[n].sL, sR = tree[n].sR, mid = (sL + sR) >> 1;
		Line low = tree[n].line, high = v;
		if (low.Get(sL) > high.Get(sL)) swap(low, high);
		rev.emplace_back(n, tree[n]);
		if (low.Get(sR) <= high.Get(sR)) {
			tree[n].line = low;
			return;
		}
		if (low.Get(mid) < high.Get(mid)) {
			tree[n].line = low;
			if (tree[n].R == -1) {
				tree[n].R = tree.size();
				tree.push_back({ -1, -1, mid + 1, sR, {0, INF} });
			}
			Update(tree[n].R, high);
		}
		else {
			tree[n].line = high;
			if (tree[n].L == -1) {
				tree[n].L = tree.size();
				tree.push_back({ -1, -1, sL, mid, {0, INF} });
			}
			Update(tree[n].L, low);
		}
	}
	ll Query(ll n, ll x) {
		if (n == -1) return INF;
		ll sL = tree[n].sL, sR = tree[n].sR, mid = (sL + sR) >> 1;
		return min(tree[n].line.Get(x), (x <= mid ? Query(tree[n].L, x) : Query(tree[n].R, x)));
	}
} LT;

void DFS(int cur, int prev, ll d) {
	ll x = A[cur], cost = B[cur] + A[cur] * d;
	dp[cur] = LT.Query(0, x) + cost;
	if (cur == 1) dp[cur] = 0;
	
	int tz = LT.tree.size();
	LT.Update(0, { -d, dp[cur] });
	vector<pair<int, LiChao::Node>> upd = LT.rev;
	LT.rev.clear();

	for (auto [next, nd] : G[cur]) {
		if (next == prev) continue;
		DFS(next, cur, d + nd);
	}

	// Revert
	for (auto [n, v] : upd) LT.tree[n] = v;
	while (LT.tree.size() > tz) LT.tree.pop_back();
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N;
	cin >> N;
	for (int i = 1; i < N; ++i) {
		ll a, b, d;
		cin >> a >> b >> d;
		G[a].emplace_back(b, d);
		G[b].emplace_back(a, d);
	}
	for (int i = 2; i <= N; ++i) cin >> B[i] >> A[i];

	DFS(1, 0, 0);

	for (int i = 2; i <= N; ++i) cout << dp[i] << ' ';
	return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'void DFS(int, int, ll)':
harbingers.cpp:73:24: warning: comparison of integer expressions of different signedness: 'std::vector<LiChao::Node>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |  while (LT.tree.size() > tz) LT.tree.pop_back();
      |         ~~~~~~~~~~~~~~~^~~~

• Subtask 1: 30 / 100