Submission #522801

#	Time	Username	Problem	Language	Result	Execution time	Memory
522801		danielliu04	Harbingers (CEOI09_harbingers)	C++17	70 / 100	1101 ms	20684 KiB

harbingers

// Link: https://oj.uz/problem/view/CEOI09_harbingers

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define lc (node<<1)+1
#define rc (node<<1)+2
#define endl '\n'
#define INF 1e18

const int max_n = 1e5+5;

int n;
vector<pair<int, int>> adj[max_n];
ll init[max_n], speed[max_n];

ll dp[max_n]; // this is the answer for this

struct line{
	ll m, b;
	ll evaluate(ll x){
		return m*x+b;
	}
	ld inter(line other){
		return (ld)(other.b - b) / (m - other.m);
	}
};
// This is the CHT Structure
line st[max_n]; 
int st_end = 0; // this is not inclusive

ll get_min_value(ll x){ // finds the min y value given an x value
	int low = 0, high = st_end - 1; // find last segment that has a left bound to the left of this x
	while(high > low){
		int mid = (high + low + 1) / 2;
		int prev = mid - 1;
		if(st[mid].inter(st[prev]) <= x) low = mid;
		else high = mid - 1;
	}
	return st[low].evaluate(x);
}

int find_pos(line new_line){
	int j = st_end; // the current last position is the first candidate
	while(j > 1 && new_line.inter(st[j-2]) < st[j-1].inter(st[j-2])) j --;
	return j;
}

void dfs(ll prefix = 0, int node = 0, int parent = -1){

	// evaluate the answer at this position first
	if(node == 0) dp[node] = 0;
	else dp[node] = get_min_value(speed[node]) + init[node] + prefix*speed[node];
	// cout << node << ' ' << dp[node] << endl;

	// insert the current line into stack
	int prev_end, pos; 
	line prev_line, new_line = {-prefix, dp[node]};

	pos = find_pos(new_line);
	prev_line = st[pos]; // save the deleted line
	prev_end = st_end;
	st[pos] = new_line;
	st_end = pos + 1;

	for(auto next: adj[node]){
		if(next.first == parent) continue;
		dfs(prefix + next.second, next.first, node);
	}

	// restore the cht to what was before
	st_end = prev_end;
	st[pos] = prev_line;
}

int main() {

	cin >> n;

	for(int i = 0; i < n-1; i ++){
		int a, b, c; cin >> a >> b >> c; a --; b --;
		adj[a].push_back({b, c}); adj[b].push_back({a, c});
	}

	for(int i = 1; i < n; i ++){
		cin >> init[i] >> speed[i];
	}

	dfs();

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

• Subtask 1: 70 / 100