Submission #742155

#	Time	Username	Problem	Language	Result	Execution time	Memory
742155		siewjh	Harbingers (CEOI09_harbingers)	C++17	100 / 100	124 ms	19656 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MAXN = 100'005;
vector<pair<int, ll>> adj[MAXN];
ll prep[MAXN], tim[MAXN], dp[MAXN], dist = 0;
struct line{
	ll m, c;
	ll eval(ll x){
		return m * x + c;
	}
};
line dq[MAXN]; int dqsz = 0;
pair<line, int> st[MAXN];
ld poi(line a, line b) {
	return (ld)(a.c - b.c) / (b.m - a.m);
}
void insert(line a, int ind) {
	int orisz = dqsz;
	int l = 1, r = dqsz - 1, ans = dqsz;
	while (l <= r){
		int m = (l + r) >> 1;
		if (poi(dq[m], a) <= poi(dq[m], dq[m - 1])) {
			ans = m;
			r = m - 1;
		}
		else l = m + 1;
	}
	st[ind] = {dq[ans], orisz};
	dq[ans] = a; dqsz = ans + 1;
}
ll query(ll x){
	if (dqsz == 0) return 0;
	int l = 0, r = dqsz - 2, ans = dqsz - 1;
	while (l <= r){
		int m = (l + r) >> 1;
		if (dq[m].eval(x) <= dq[m + 1].eval(x)){
			ans = m;
			r = m - 1;
		}
		else l = m + 1;
	}
	return dq[ans].eval(x);
}
void rollback(int ind){
	line a = st[ind].first; int psz = st[ind].second;
	dq[dqsz - 1] = a;
	dqsz = psz;
}
void dfs(int x, int par){
	if (x == 1) dp[x] = 0;
	else dp[x] = prep[x] + dist * tim[x] + query(tim[x]);
	insert({-dist, dp[x]}, x);
	for (auto nxt : adj[x]){
		int nn = nxt.first; ll nd = nxt.second;
		if (nn == par) continue;
		dist += nd;
		dfs(nn, x);
		dist -= nd;
	}
	rollback(x);
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int nodes; cin >> nodes;
	for (int i = 1; i < nodes; i++){
		int a, b; ll d; cin >> a >> b >> d;
		adj[a].push_back({b, d});
		adj[b].push_back({a, d});
	}
	for (int i = 2; i <= nodes; i++) cin >> prep[i] >> tim[i];
	dfs(1, -1);
	for (int i = 2; i <= nodes; i++) cout << dp[i] << ' ';
}

• Subtask 1: 100 / 100