Submission #400028

#	Time	Username	Problem	Language	Result	Execution time	Memory
400028		hltk	Harbingers (CEOI09_harbingers)	C++17	70 / 100	1093 ms	27356 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
const long INF = 1e18;
int n, s[100100], t[100100];
long dp[100100];
vector<pair<int, int>> g[100100];
struct Line {
	long m, c;
	long operator()(long x) { return m * x + c; }
};
long intersect(Line a, Line b) {
	long num = b.c - a.c, dem = a.m - b.m;
	return num / dem - ((num ^ dem) < 0 && num % dem);
}
vector<pair<long, Line>> cht{{-INF, {0, 0}}};
long query(long x) {
	return prev(lower_bound(cht.begin(), cht.end(), pair{x, Line{}}, [&](auto a, auto b) {
		return a.first < b.first;
	}))->second(x);
}
void dfs(int u, int p, long cd) {
	vector<Line> popped;
	if (u != 1) {
		dp[u] = -query(t[u]) + cd * t[u] + s[u];
		auto l = Line{cd, -dp[u]};
		while ((int) cht.size() >= 2) {
			auto a = cht[cht.size() - 2].second;
			auto b = cht[cht.size() - 1].second;
			if (intersect(a, b) >= intersect(b, l)) {
				popped.push_back(cht.back().second);
				cht.pop_back();
			} else break;
		}
		cht.emplace_back(intersect(cht.back().second, l), l);
	}
	for (auto [v, d] : g[u]) {
		if (v == p) continue;
		dfs(v, u, cd + d);
	}
	if (u != 1) {
		cht.pop_back();
		while (!popped.empty()) {
			cht.emplace_back(intersect(cht.back().second, popped.back()), popped.back());
			popped.pop_back();
		}
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 1, u, v, d; i <= n - 1; ++i) {
		scanf("%d %d %d", &u, &v, &d);
		g[u].emplace_back(v, d);
		g[v].emplace_back(u, d);
	}
	for (int i = 2; i <= n; ++i) scanf("%d %d", s + i, t + i);
	dfs(1, -1, 0);
	for (int i = 2; i <= n; ++i) printf("%ld%c", dp[i], i == n ? '\n' : ' ');
}
// f_j(x) := -dp[j] + dep[j] * x
//   dp[j] + (d - x) t_i + s_i
// = dp[j] - x * t_i + d * t_i + s_i
// = -f_j(t_i) + d * t_i + s_i

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
harbingers.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |   scanf("%d %d %d", &u, &v, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:55:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |  for (int i = 2; i <= n; ++i) scanf("%d %d", s + i, t + i);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 70 / 100