oj.uz

Submission #522802

# Submission time Handle Problem Language Result Execution time Memory
522802 2022-02-05T22:55:14 Z danielliu04 Harbingers (CEOI09_harbingers) C++17
100 / 100
 190 ms 20588 KB 
// 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, ll>> 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){
	if(st_end < 2 || new_line.inter(st[st_end-2]) > st[st_end-1].inter(st[st_end-2])) return st_end;
	int low = 1, high = st_end - 1;
	while(high > low){
		int mid = (low + high) / 2;
		// check if new_line can replace mid
		if(new_line.inter(st[mid-1]) <= st[mid].inter(st[mid-1])) high = mid;
		else low = mid + 1;
	}
	return low;
}

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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2692 KB Output is correct
2 Correct 7 ms 3148 KB Output is correct
3 Correct 81 ms 10348 KB Output is correct
4 Correct 107 ms 14136 KB Output is correct
5 Correct 145 ms 17228 KB Output is correct
6 Correct 189 ms 20588 KB Output is correct
7 Correct 103 ms 11008 KB Output is correct
8 Correct 190 ms 16152 KB Output is correct
9 Correct 184 ms 17884 KB Output is correct
10 Correct 161 ms 16528 KB Output is correct