oj.uz

Submission #522801

# Submission time Handle Problem Language Result Execution time Memory
522801 2022-02-05T22:41:46 Z danielliu04 Harbingers (CEOI09_harbingers) C++17
70 / 100
 1000 ms 20684 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, 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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 5 ms 3044 KB Output is correct
3 Correct 77 ms 10548 KB Output is correct
4 Correct 106 ms 14120 KB Output is correct
5 Correct 142 ms 17508 KB Output is correct
6 Correct 164 ms 20684 KB Output is correct
7 Correct 102 ms 11472 KB Output is correct
8 Execution timed out 1101 ms 15300 KB Time limit exceeded
9 Execution timed out 1052 ms 17172 KB Time limit exceeded
10 Execution timed out 1065 ms 16084 KB Time limit exceeded