Submission #492702

#	Time	Username	Problem	Language	Result	Execution time	Memory
492702		zhougz	Harbingers (CEOI09_harbingers)	C++17	100 / 100	121 ms	22364 KiB

harbingers

/**
 *    author: chowgz
 *    created: 14/03/2021 21:31:52
**/
#include <bits/stdc++.h>

using namespace std;

constexpr int MAXN = 100'000;

int prep[MAXN], speed[MAXN], dist[MAXN], ints[MAXN + 1];
long long ans[MAXN];
bool visited[MAXN];
vector<pair<int, int>> v[MAXN];

struct Line {
	int m;
	long long c;
	double operator^(const Line &rhs) {
		return ((double)c - rhs.c) / ((double)rhs.m - m);
	}
	long long operator()(int x) {
		return (long long)m * x + c;
	}
};

struct ConvexHull {
	Line lines[MAXN + 1];
	void insert(Line line, int &r, Line &bak_line) {
		r = lower_bound(ints + 1, ints + r, line, [&](const int &idx, const Line &line) {
			return (lines[idx - 1] ^ lines[idx]) < (lines[idx] ^ line);
		}) - ints;
		bak_line = lines[r];
		lines[r] = line;
	}
	long long query(int x, int r) {
		return lines[lower_bound(ints, ints + r - 1, x, [&](const int &idx, const int& x){
			return (lines[idx] ^ lines[idx + 1]) < x;
		}) - ints](x);
	}
	void restore(int r, Line line) {
		lines[r] = line;
	}
} hull;

void dfs(int idx, int r) {
	visited[idx] = true;
	ans[idx] = (long long)speed[idx] * dist[idx] + prep[idx] + min(0LL, hull.query(speed[idx], r));
	Line bak_line;
	hull.insert(Line{-dist[idx], ans[idx]}, r, bak_line);
	for (const auto &z : v[idx]) {
		if (visited[z.first]) {
			continue;
		}
		dist[z.first] = dist[idx] + z.second;
		dfs(z.first, r + 1);
	}
	hull.restore(r, bak_line);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	iota(ints, ints + MAXN + 1, 0);
	int n;
	cin >> n;
	for (int i = 0, a, b, d; i < n - 1; i++) {
		cin >> a >> b >> d;
		a--;
		b--;
		v[a].emplace_back(b, d);
		v[b].emplace_back(a, d);
	}
	for (int i = 1; i < n; i++) {
		cin >> prep[i] >> speed[i];
	}
	Line bak_line;
	int r = 0;
	hull.insert(Line{0, 0}, r, bak_line);
	dfs(0, 1);
	cout << ans[1];
	for (int i = 2; i < n; i++) {
		cout << ' ' << ans[i];
	}
	cout << '\n';
	return 0;
}

• Subtask 1: 100 / 100