Submission #528184

#	Time	Username	Problem	Language	Result	Execution time	Memory
528184		sidon	Harbingers (CEOI09_harbingers)	C++17	20 / 100	184 ms	65544 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define sp << ' ' <<
#define nl << '\n'

const int LIM = 1e9, INF = 2e9;

struct Line {
	int m, c;
	Line(int M = 0, int C = INF) : m(M), c(C) {}
	int operator()(int x) {
		return m * x + c;
	}
};

struct LiChaoTree {
	Line v;
	LiChaoTree *L = NULL, *R = NULL;
	void insert(Line u, auto &rb, int l = 0, int r = LIM + 1) {
		int m = (l + r) / 2;
		if(u(m) < v(m)) {
			rb.emplace_back(&v, v);
			swap(u, v);
		}
		if(r - l < 2) return;
		u.m > v.m ? (L ? : L = new LiChaoTree)->insert(u, rb, l, m):
					(R ? : R = new LiChaoTree)->insert(u, rb, m, r);
	}
	int query(int x, int l = 0, int r = LIM + 1) {
		if(r - l < 2) return v(x);
		int m = (l + r) / 2;
		return min(v(x), x < m ? (L ? L->query(x, l, m) : INF) : (R ? R->query(x, m, r) : INF));
	}
} lt;

const int Z = 1e5+1;

int N, S[Z], V[Z], dp[Z];
vector<array<int, 2>> g[Z];

void dfs(int u, int p, int d) {
	vector<pair<Line*, Line>> rb;
	dp[u] = u ? lt.query(V[u]) + S[u] + V[u] * d : int();

	lt.insert(Line(-d, dp[u]), rb);

	// cout << 

	// cerr << u sp p sp d sp size(g[u]) nl;
	// cerr << u sp p sp d nl;

	for(auto &[v, w] : g[u]) if(v != p) {
		// cerr << u sp v sp d sp w nl;
		dfs(v, u, d + w);
	}

	for(int i = size(rb); i--; )
		(*rb[i].first) = rb[i].second;
}

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];

	dfs(0, 0, 0);

	for(int i = 1; i < N; ++i)
		cout << dp[i] << ' ';
}

Compilation message (stderr)

harbingers.cpp:20:22: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 |  void insert(Line u, auto &rb, int l = 0, int r = LIM + 1) {
      |                      ^~~~

• Subtask 1: 20 / 100