Submission #337007

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
337007	2020-12-17T21:06:08 Z	penguinhacker	Harbingers (CEOI09_harbingers)	C++14	100 / 100	148 ms	25548 KB

harbingers

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

#define ll long long
#define ar array

int binary_search(function<bool(int)> f, int lb, int rb) {
	while(lb < rb) {
		int mb = (lb + rb + 1) / 2;
		if (f(mb)) lb = mb;
		else rb = mb - 1;
	} 
	return lb;
}

const int mxN = 100000;
int n, delay[mxN], speed[mxN];
ll d[mxN], dp[mxN];
vector<pair<int, int>> adj[mxN];

struct Line {
	ll m = 0, b = 0;
	ll eval(ll x) {return m * x + b;}
};
double isect(Line& a, Line& b) {
	return (double)(a.b - b.b) / (b.m - a.m);
}

int sz = 1;
Line q[mxN];

void dfs(int u, int p) {
	int ind = binary_search([&](int i) {return speed[u] > isect(q[i], q[i - 1]);} , 0, sz - 1);
	dp[u] = d[u] * speed[u] + delay[u] + q[ind].eval(speed[u]);

	Line cur = {-d[u], dp[u]};
	int l = 1, r = sz;
	while(l < r) {
		int mid = (l + r) / 2;
		if (isect(cur, q[mid - 1]) < isect(q[mid], q[mid - 1])) r = mid;
		else l = mid + 1;
	}
	ind = l;
	swap(cur, q[ind]);
	int new_size = ind + 1;
	swap(sz, new_size);

	for (pair<int, int> v : adj[u]) if (v.first != p) {
		d[v.first] = d[u] + v.second;
		dfs(v.first, u);
	}

	swap(cur, q[ind]);
	swap(sz, new_size);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i < n; ++i) {
		int a, b, c; cin >> a >> b >> c, --a, --b;
		adj[a].emplace_back(b, c);
		adj[b].emplace_back(a, c);
	}
	for (int i = 1; i < n; ++i) {
		cin >> delay[i] >> speed[i];
	}
	for (pair<int, int> p : adj[0]) {
		d[p.first] = p.second;
		dfs(p.first, 0);
	}
	for (int i = 1; i < n; ++i) {
		cout << dp[i] << " ";
	}
	return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2668 KB	Output is correct
2	Correct	5 ms	3308 KB	Output is correct
3	Correct	57 ms	12652 KB	Output is correct
4	Correct	82 ms	17132 KB	Output is correct
5	Correct	104 ms	21356 KB	Output is correct
6	Correct	134 ms	25548 KB	Output is correct
7	Correct	71 ms	12908 KB	Output is correct
8	Correct	148 ms	18536 KB	Output is correct
9	Correct	146 ms	21356 KB	Output is correct
10	Correct	123 ms	19688 KB	Output is correct