Submission #1212809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212809		g4yuhg	Harbingers (CEOI09_harbingers)	C++20	100 / 100	72 ms	19880 KiB

harbingers

//Huyduocdithitp
#include <bits/stdc++.h>
#define int long long
typedef long long ll;
#define endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1e18
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 19
#define N 100005
using namespace std;
struct Line {
	ll a, b;
};
struct Node {
	pii cu;
	ll pos, sz;
};
vector<Node> undo;
ll n, d[N], F[N];
vector<pii> adj[N];
ll S[N], V[N], sz = 0;
Line A[200005];
ll ptr = 0;
bool bad(Line l1, Line l2, Line l3) {
	return double(l3.b - l1.b) / (l1.a - l3.a) < double(l2.b - l1.b) / (l1.a - l2.a);
}
void add(ll u, ll v) {
	Line xet = {u, v};
	ll l = 1, r = sz - 1, ans = sz;
	while (l <= r) {
		ll mid = (l + r) / 2;
		if (bad(A[mid - 1], A[mid], xet)) {
			ans = mid;
			r = mid - 1;
		}
		else {
			l = mid + 1;
		}
	}
	undo.push_back({{A[ans].a, A[ans].b}, ans, sz});
	A[ans] = xet;
	sz = ans + 1;
}
void Undo() {
	sz = undo.back().sz; A[undo.back().pos] = {undo.back().cu.fi, undo.back().cu.se};
	undo.pop_back();
}
ll cal(Line U, ll x) {
	return U.a * x + U.b;
}
ll qr(ll x) {
	if (sz == 0) return 0;
	ll ans = cal(A[0], x);
	/*for (int i = 1; i < sz; i ++) {
		ans = min(ans, cal(A[i], x));
	}
	return ans;*/
	ll l = 1, r = sz - 1;
	while (l <= r) {
		ll mid = (l + r) / 2;
		if (cal(A[mid], x) < cal(A[mid - 1], x)) {
			ans = min(ans, cal(A[mid], x));
			l = mid + 1;
		}
		else {
			r = mid - 1;
		}
	}
	return ans;
}
void dfs(ll u, ll parent) {
	if (u == 1) {
		add(0, 0);
	}
	else {
		F[u] = qr(V[u]) + S[u] + V[u] * d[u];
		add(-d[u], F[u]);
	}
	for (auto v : adj[u]) {
		if (v.fi == parent) continue;
		d[v.fi] = d[u] + v.se;
		dfs(v.fi, u);
	}
	if (u != 1) {
		Undo();
	}
}
signed main(void) {
    faster;
    cin >> n;
    for (int i = 1; i <= n - 1; i ++) {
    	ll u, v, w;
    	cin >> u >> v >> w;
    	adj[u].push_back({v, w});
    	adj[v].push_back({u, w});
    }
    for (int i = 2; i <= n; i ++) {
    	cin >> S[i] >> V[i];
    }
    dfs(1, 1);
    for (int i = 2; i <= n; i ++) {
    	cout << F[i] << " ";
    }
    return 0;
}

• Subtask 1: 100 / 100