Submission #752725

#	Time	Username	Problem	Language	Result	Execution time	Memory
752725		Tob	Harbingers (CEOI09_harbingers)	C++14	100 / 100	206 ms	20280 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, siz;
ll a[N], b[N], dp[N], res[N];
vector <pii> adj[N];
pii v[N];

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

void DP(int x, int p, ll d) {
	int lo = 0, hi = siz-1, poc = siz;
	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 (siz) mn = v[lo].F * b[x] + v[lo].S;
	mn += b[x]*d + a[x];
	pii pp = {-d, mn};
	lo = 1, hi = siz;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		if (ccw(v[mid-1], v[mid], pp)) hi = mid;
		else lo = mid+1;
	}
	if (siz == 0) lo = 0;
	pii po = v[lo];
	v[lo] = pp;
	siz = lo+1;
	
	res[x] = mn;
	for (auto it : adj[x]) {
		if (it.F == p) continue;
		DP(it.F, x, d + it.S);
	}
	
	siz--;
	v[siz] = po;
	siz = poc;
}

int main()
{
	cin >> n;
	
	for (int i = 1; i < n; i++) {
		int x, y;
		ll 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: 100 / 100