Submission #752650

#	Time	Username	Problem	Language	Result	Execution time	Memory
752650		Tob	Harbingers (CEOI09_harbingers)	C++14	50 / 100	1088 ms	18740 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;

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) {
	ll mn = 1e18;
	for (int i = 0; i < v.size(); i++) {
		mn = min(mn, v[i].F * b[x] + v[i].S);
	}
	if (v.empty()) mn = 0;
	mn += b[x]*d + a[x];
	pii pp = {-d, mn};
	while (v.size() > 1 && ccw(v[v.size()-2], v.back(), pp)) v.pop_back();
	v.pb(pp);
	
	res[x] = mn;
	for (auto it : adj[x]) {
		if (it.F == p) continue;
		DP(it.F, x, d + it.S);
	}
}

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;
}

Compilation message (stderr)

harbingers.cpp: In function 'void DP(int, int, ll)':
harbingers.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~

• Subtask 1: 50 / 100