Submission #490903

#	Time	Username	Problem	Language	Result	Execution time	Memory
490903		thiago_bastos	Harbingers (CEOI09_harbingers)	C++17	0 / 100	1095 ms	26576 KiB

harbingers

#include "bits/stdc++.h"

using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned;
using i16 = short;
using u16 = unsigned short;
using ld = long double;
using ii = pair<int, int>;

using T = tuple<int, i64, i64>;

int n;

vector<vector<ii>> g;
vector<i64> pre, dp;
stack<T> changes;
deque<pair<i64, i64>> dq;
vector<int> s, vel;

ld point(i64 a0, i64 b0, i64 a1, i64 b1) {
	return (b1 - b0) / ld(a0 - a1);
}

void dfs(int u, int p) {
	
	if(u != p) {
		int lo = 1, hi = (int)dq.size() - 1;
		while(lo < hi) {
			int mid = (lo + hi) / 2;
			auto [a0, b0] = dq[mid - 1];
			auto [a1, b1] = dq[mid];
			if(point(a0, b0, a1, b1) >= vel[u]) hi = mid;
			else lo = mid + 1;
		}
		hi = max(0, hi - 1);
		dp[u] = s[u] + vel[u] * (pre[u] + dq[hi].first) + dq[hi].second;
	}
	
	while((int)dq.size() >= 2) {
		int n = dq.size();
		auto [a0, b0] = dq[n - 1];
		auto [a1, b1] = dq[n - 2];
		if(point(-pre[u], dp[u], a0, b0) > point(a0, b0, a1, b1)) break;
		changes.emplace(u, a0, b0);
		dq.pop_back();
	}
	
	dq.emplace_back(-pre[u], dp[u]);
	
	for(auto [v, d] : g[u]) {
		if(v == p) continue;
		pre[v] = pre[u] + d;
		dfs(v, u);
	}
	
	dq.pop_back();
	
	while(!changes.empty()) {
		auto [_, a, b] = changes.top();
		if(_ != u) break;
		changes.pop();
		dq.emplace_back(a, b);
	}
}

void solve() {

	cin >> n;
	
	g.resize(n);
	pre.resize(n);
	dp.resize(n);
	s.resize(n);
	vel.resize(n);
	
	for(int i = 1; i < n; ++i) {
		int u, v, d;
		cin >> u >> v >> d;
		--u, --v;
		g[u].emplace_back(v, d);
		g[v].emplace_back(u, d);
	}
	
	s[0] = vel[0] = 0;
	for(int i = 1; i < n; ++i) cin >> s[i] >> vel[i];
	
	pre[0] = dp[0] = 0;
	dfs(0, 0);
	
	for(int i = 1; i < n; ++i) cout << dp[i] << ' ';
	cout << '\n';
}
 
int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
 	return 0;
}

• Subtask 1: 0 / 100