oj.uz

Submission #528227

# Submission time Handle Problem Language Result Execution time Memory
528227 2022-02-19T17:47:00 Z sidon Harbingers (CEOI09_harbingers) C++17
100 / 100
 158 ms 28624 KB 
#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)
#define comp(X, Y, Z) (eval(Z, X) < eval(Z, Y))

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(comp(sU, v[u], vals[m]))
			rb.emplace_back(u, v[u]), swap(sU, v[u]);
		if(comp(v[u], sU, vals[l]) && comp(v[u], sU, vals[r-1]))
			return;

		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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 3 ms 3332 KB Output is correct
3 Correct 48 ms 13624 KB Output is correct
4 Correct 96 ms 24160 KB Output is correct
5 Correct 110 ms 22012 KB Output is correct
6 Correct 108 ms 20608 KB Output is correct
7 Correct 75 ms 10432 KB Output is correct
8 Correct 125 ms 24124 KB Output is correct
9 Correct 145 ms 28624 KB Output is correct
10 Correct 158 ms 26280 KB Output is correct