Submission #752671

#	Time	Username	Problem	Language	Result	Execution time	Memory
752671		Tob	Harbingers (CEOI09_harbingers)	C++14	70 / 100	1092 ms	29224 KiB

harbingers

#include<bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <pii, ll> piii;

const int N = 1e5 + 7;

int n;
ll a[N], b[N], dp[N], res[N];
vector <pii> adj[N];
vector <pii> v;
stack <pii> st;

int ccw(pii x, pii y, pii z) {
	return (x.F*(y.S-z.S) + y.F*(z.S-x.S) + z.F*(x.S-y.S) >= 0);
}

void DP(int x, int p, ll d) {
	int lo = 0, hi = v.size()-1;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		ll xx = v[mid].F * b[x] + v[mid].S, yy = v[mid+1].F * b[x] + v[mid+1].S;
		if (xx > yy) lo = mid+1;
		else hi = mid;
	}
	ll mn = 0;
	if (!v.empty()) mn = v[lo].F * b[x] + v[lo].S;
	mn += b[x]*d + a[x];
	pii pp = {-d, mn};
	int cnt = 0;
	while (v.size() > 1 && ccw(v[v.size()-2], v.back(), pp)) {
		st.push(v.back());
		v.pop_back();
		cnt++;
	}
	v.pb(pp);
	
	res[x] = mn;
	for (auto it : adj[x]) {
		if (it.F == p) continue;
		DP(it.F, x, d + it.S);
	}
	
	v.pop_back();
	for (int i = 0; i < cnt; i++, st.pop()) v.pb(st.top());
}

int main()
{
	cin >> n;
	
	for (int i = 1; i < n; i++) {
		ll x, y, d; cin >> x >> y >> d;
		adj[x].pb({y, d});
		adj[y].pb({x, d});
	}
	
	for (int i = 2; i <= n; i++) {
		cin >> a[i] >> b[i];
	}
	
	DP(1, 0, 0);
	
	for (int i = 2; i <= n; i++) cout << res[i] << " ";

	return 0;
}

• Subtask 1: 70 / 100