Submission #879471

#	Time	Username	Problem	Language	Result	Execution time	Memory
879471		LarryMiller	Harbingers (CEOI09_harbingers)	C++11	100 / 100	85 ms	25176 KiB

harbingers

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;

vector<pair<ll, ll>> e[100001];

struct Line {
	ll m, b;

	Line(ll m = 0, ll b = 0) : m(m), b(b) {}

	/** Evaluates the linear function at position x */
	ll operator()(ll x) { return m * x + b; }

	/** Returns the x-coordinate of the intersection of two lines */
	friend ld intersect(Line l1, Line l2) {
		return (ld)(l2.b - l1.b) / (ld)(l1.m - l2.m);
	}
};


Line stk[100001];   // convex hull of lines
int stk_max = 0;

ll h[100001], w[100001], dp[100001], s[100001], v[100001];
bool visited[100001];

ll line_min(ll x) {
	// binary search for min value
	int l = 0, r = stk_max - 1;
	while (l < r) {
		int m = (l + r) / 2;
		if (intersect(stk[m], stk[m + 1]) < x) {
			l = m + 1;
		} else {
			r = m;
		}
	}
	return stk[l](x);
}

ll remove_pos(Line line) {
	// check if hull is trivial or if line belongs at the end
	if (stk_max < 2 || intersect(line, stk[stk_max - 1]) >=
	                       intersect(stk[stk_max - 1], stk[stk_max - 2])) {
		return stk_max;
	}

	// begin at l = 1 because we need to check intersection between k and k - 1
	int l = 1, r = stk_max - 1;
	while (l < r) {
		int m = (l + r) / 2;
		if (intersect(line, stk[m]) < intersect(stk[m], stk[m - 1])) {
			r = m;
		} else {
			l = m + 1;
		}
	}
	return l;
}

// void calc_dist(int u){
//     for (auto next : e[u]){
// 		if (!visited[next.first]){
// 			d[next.first] = d[u] + next.second;
// 			visited[next.first] = 1;
//         	calc_dist(next.first);
// 		}
//     }
//     return;
// }

void dfs(int u, int p, int d){
	int prev_max, prev_pos;
	Line prev_line;
	if (u == 1) {
		dp[u] = 0;
		stk[stk_max++] = {0, 0};
	} 
	else {
		dp[u] = line_min(v[u]) + d * v[u] +
		              s[u]; 
		Line l(
		    -d,
		    dp[u]);
		prev_max = stk_max; 
		prev_pos = stk_max =
		    remove_pos(l);
		prev_line =
		    stk[stk_max];
		stk[stk_max++] = l; 
	}
    for (auto [nex, w] : e[u]) {
		if (nex != p) { dfs(nex, u, d + w); }
	}

	if (u != 1) {
		stk_max = prev_max;
		stk[prev_pos] = prev_line;
	}
    return;
}

int main() {
    // freopen( "Harbingers.in", "r", stdin);
    // freopen( "Harbingers.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 2; i <= n; i++){
		int f, t, w;
        cin >> f >> t >> w;
        e[f].emplace_back(t,w);
		e[t].emplace_back(f,w);
    };
	for (int i = 2; i <= n; i++) {
		cin >> s[i] >> v[i];
	}
    dfs(1, 0, 0);

    for (int i = 2; i <= n; i++) { cout << dp[i] << ' '; }
	cout << '\n';
}

Compilation message (stderr)

harbingers.cpp: In function 'void dfs(int, int, int)':
harbingers.cpp:94:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   94 |     for (auto [nex, w] : e[u]) {
      |               ^

• Subtask 1: 100 / 100