제출 #176048

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
176048		qwerty234	Harbingers (CEOI09_harbingers)	C++14	20 / 100	213 ms	65540 KiB

harbingers

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define f first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>


using namespace std;

const int N = 1e5 + 123;
const ll mod = 1e9 + 7;
const ll inf = 1e18;


struct line {
	ll k, b;
};


struct node {
	node *l, *r;
	line cur;
	node (node *v, line x) {
		if (!v) {
			cur = x;
			l = NULL;
			r = NULL;
		} else {
			cur = v->cur;
			l = v->l;
			r = v->r;
		}
	}
};


node *t[N];
ll lb, rb;


ld getld(line cur, ll x) {
	x *= 1.0;
	return cur.k * 1.0 * x + cur.b * 1.0;
}


ll getll(line cur, ll x) {
	return cur.k * x + cur.b;
}


ll getmid(ll tl, ll tr) {
	return ((tl + tr + 2ll * inf) / 2ll) - inf;
}


void add(node *&v, ll tl, ll tr, line nw) {
	if (!v) {
		v = new node(v, nw);
		return;
	}
	v = new node(v, nw);
	ll tm = getmid(tl, tr);
	bool left = getld(v->cur, tl) > getld(nw, tl);
	bool mid = getld(v->cur, tm) > getld(nw, tm);
	bool right = getld(v->cur, tr) > getld(nw, tr);
	if ((left && mid) || (right && mid))
		swap(v->cur, nw);
	if (tl == tr) return;	
	if (left == mid)
		add(v->r, tm + 1, tr, nw);
	else
		add(v->l, tl, tm, nw);		
}


ll get(node *&v, ll tl, ll tr, ll x) {
	if (!v) return inf;
	if (tl == tr) return getll(v->cur, x);
	ll res, tm = getmid(tl, tr);
	if (x <= tm)
		res = get(v->l, tl, tm, x);
	else
		res = get(v->r, tm + 1, tr, x);
	return min(res, getll(v->cur, x));	
}


void clearr(node *&v) {
	if (!v) return;
	clearr(v->l);
	clearr(v->r);
	v = NULL;
}


ll n, s[N], v[N], dp[N];
vector <pll> g[N];


void dfs(ll u, ll p, ll d) {
	line tmp;
	dp[u] = s[u] + v[u] * d + get(t[p], lb, rb, v[u]);
	tmp.k = -d; tmp.b = dp[u];
	t[u] = t[p];
	add(t[u], lb, rb, tmp);
	for (pll to : g[u])
		if (to.f != p)
			dfs(to.f, u, d + to.se);
}


int main() {
	ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
	//freopen("input.txt", "r", stdin);
//	freopen("harbingers.in", "r", stdin);
//	freopen("harbingers.out", "w", stdout);
	line tmp;
	lb = 0; rb = 1000000010;
	cin >> n;
	for (int i = 1; i < n; i++) {
		ll u, v, d;
		cin >> u >> v >> d;
		g[u].pb({v, d});
		g[v].pb({u, d});
	}
	for (int i = 2; i <= n; i++)
		cin >> s[i] >> v[i];
	dp[1] = 0;
	tmp.k = 0; tmp.b = 0;
	add(t[1], lb, rb, tmp);
	for (pll to : g[1])
		dfs(to.f, 1, to.se);
	for (int i = 2; i <= n; i++)
		cout << dp[i] << " ";
	return 0;
}

• Subtask 1: 20 / 100