제출 #474518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
474518		pure_mem	Harbingers (CEOI09_harbingers)	C++14	100 / 100	148 ms	22748 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], 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 l = 2, r = sz;

	while(l <= r) {
		int m = (l + r) / 2;
		if(bad(CHT[m - 1], CHT[m], v))
			r = m - 1;
		else 
			l = m + 1;
	}
	int bfr = CHT[r + 1];
	int bfr_sz = sz;

	sz = r + 1, CHT[r + 1] = 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 = bfr_sz, CHT[r + 1] = bfr;
}

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: 100 / 100