Submission #528223

#	Time	Username	Problem	Language	Result	Execution time	Memory
528223		sidon	Harbingers (CEOI09_harbingers)	C++17	80 / 100	140 ms	65540 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
#define i64 int64_t
#define sp << ' ' <<
#define nl << '\n'
using T = pair<int, i64>;
 
const i64 INF = 2e9;
const int Z = 1e5+1;
 
#define eval(X, Y) (i64(Y.first) * X + Y.second)

vector<pair<int, T>> rb;
int vals[1<<18];

T sU; int sV;
#define m ((l + r) / 2)
struct LiChaoTree {
	T v[1<<18];
	void insert(int u, int l, int r) {
		if(eval(vals[m], sU) < eval(vals[m], v[u]))
			rb.emplace_back(u, v[u]), swap(sU, v[u]);

		if(r - l < 2) return;
		sU.first > v[u].first ? insert(2*u+1, l, m) : insert(2*u+2, m, r);
	}
	void insert(T u, int lim) {
		sU = u; insert(0, 0, lim);
	}
	i64 query(int u, int l, int r) {
		if(r - l < 2) return eval(vals[sV], v[u]);
		return min(eval(vals[sV], v[u]), sV < m ? query(2*u+1, l, m) : query(2*u+2, m, r));
	}
	i64 query(int x, int lim) {
		sV = x;
		return query(0, 0, lim);
	}
} lt;
 
int N, S[Z];
i64 V[Z]; //dp 
vector<array<int, 2>> g[Z];
int d;
 
void dfs(int u) {
	size_t rbP = size(rb);

	V[u] = lower_bound(vals, vals + N - 1, V[u]) - vals;

	V[u] = u ? lt.query(V[u], N - 1) + i64(S[u]) + i64(vals[V[u]]) * i64(d) : i64();
	lt.insert({-d, V[u]}, N-1);
 
	for(auto &[v, w] : g[u]) {
		for(auto i = begin(g[v]); ; ++i) {
			if((*i)[0] == u) {
				g[v].erase(i);
				break;
			}
		}
		d += w;
		dfs(v);
		d -= w;
	}
 
	while(size(rb) > rbP) {
		lt.v[rb.back().first] = rb.back().second;
		rb.pop_back();
	}
}
 
signed main() {
	cin.tie(0)->sync_with_stdio(0);
 
	cin >> N;
 
	for(int i = 1; i < N; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		--u, --v;
		g[u].push_back({v, w});
		g[v].push_back({u, w});
	}
 
	for(int i = 1; i < N; ++i) {
		cin >> S[i] >> V[i];
		vals[i-1] = V[i];
	}

	sort(vals, vals + N - 1);
 
	dfs(0);
 
	for(int i = 1; i < N; ++i)
		cout << V[i] << ' ';
}

• Subtask 1: 80 / 100