Submission #474517

#	Time	Username	Problem	Language	Result	Execution time	Memory
474517		pure_mem	Harbingers (CEOI09_harbingers)	C++14	70 / 100	1093 ms	25656 KiB

harbingers

#include <bits/stdc++.h>

#define X first
#define Y second
#define ll long long
#define MP make_pair

using namespace std;

const int N = 1e5 + 123;
const ll INF = 1e18;

typedef pair<ll, ll> Line;

ll f(Line me, ll x) {
	return me.X * x + me.Y;
}

int CHT[N], his[N], ptr, n, sz;
vector< pair<int, ll> > g[N];
ll dp[N], d[N], sp[N], sl[N];
Line cf[N];

ll get(ll x) {
	int l = 1, r = sz - 1;
	while(l <= r) {
		int m = (l + r) / 2;
		if(f(cf[CHT[m]], x) < f(cf[CHT[m + 1]], x))
			r = m - 1;
		else 
			l = m + 1;
	}
	return f(cf[CHT[r + 1]], x);
}

bool bad(int x, int y, int z) {
	return (cf[x].Y - cf[y].Y) * 1.0 / (cf[y].X - cf[x].X) >= (cf[x].Y - cf[z].Y) * 1.0 / (cf[z].X - cf[x].X); 
}

void dfs(int v, int pr) {
	if(pr != -1) {
		dp[v] = get(sp[v]) + sl[v] + sp[v] * d[v];
	}
	cf[v] = {-d[v], dp[v]};
	int tl = ptr;
	while(sz > 1 && bad(CHT[sz - 1], CHT[sz], v))
		his[ptr++] = CHT[sz--];
	CHT[++sz] = v;
	for(pair<int, ll> to: g[v]) {
		if(to.X == pr) continue;
		d[to.X] = d[v] + to.Y, dfs(to.X, v);
	}
	sz--;
	while(ptr > tl)
		CHT[++sz] = his[--ptr];
}

int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	for(int i = 1, x, y, z;i < n;i++) {
		cin >> x >> y >> z;
		g[x].push_back({y, z});
		g[y].push_back({x, z});
	}
	for(int i = 2;i <= n;i++)
		cin >> sl[i] >> sp[i];
	dfs(1, -1);
	for(int i = 2;i <= n;i++)
		cout << dp[i] << " ";
}

• Subtask 1: 70 / 100