Submission #399526

#	Time	Username	Problem	Language	Result	Execution time	Memory
399526		nikatamliani	Harbingers (CEOI09_harbingers)	C++14	0 / 100	190 ms	65540 KiB

harbingers

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 2e5+10, oo = 4e18;
vector<pair<int, int>> edges[N];
ll p[N], s[N], v[N], sum[N], dp[N], n;
void mini(ll &x, ll y) {
	if(x > y) {
		x = y;
	}
}
struct line {
	ll k, b;
	line(ll _k, ll _b) : k(_k), b(_b) {}
	line() : line(0, 4e18) {}
	ll f(ll x) {
		return k*x + b;
	}
};
struct lichao {
	vector<array<int, 2>> children;
	vector<line> t;
	stack<pair<int, line>> ops;
	int nodes, size;
	lichao(int _size = 1e9) {
		size = _size;
		nodes = 0;
		create_node();
	}
	int create_node() {
		children.push_back({-1, -1});
		t.push_back(line());
		return nodes++;
	}
	void rollback(int T) {
		assert(T >= 0);
		while((int)ops.size() > T) {
			pair<int, line> p = ops.top(); ops.pop();
			t[p.first] = p.second;
		}
	}
	int add_line(ll l, ll r, line ln, int pos) {
		if(pos == -1) {
			pos = create_node();
		}
		ll m = l + r >> 1;
		bool lft = t[pos].f(l) < ln.f(l);
		bool mid = t[pos].f(m) < ln.f(m);
		if(lft == mid && !lft) {
			ops.push({pos, t[pos]});
			swap(t[pos], ln);
		} 
		if(lft != mid && !mid) {
			ops.push({pos, t[pos]});
			swap(t[pos], ln);
		}
		if(l == r) return pos;
		if(lft == mid) {
			children[pos][1] = add_line(m+1, r, ln, children[pos][1]);
		} else {
			children[pos][0] = add_line(l, m, ln, children[pos][0]);
		}
		return pos;
	}
	ll get_min(ll l, ll r, ll x, int pos) {
		if(pos == -1 || l > x || r < x) return oo;
		ll me = t[pos].f(x);
		if(l == r) return me;
		ll m = l + r >> 1;
		ll lft = get_min(l, m, x, children[pos][0]);
		ll rgh = get_min(m+1, r, x, children[pos][1]);
		return min({me, lft, rgh});
	}
	void add_line(line l) {
		add_line(1, size, l, 0);
	}
	ll get_min(ll x) {
		return get_min(1, size, x, 0);
	}
} t;
void dfs(int x, int p) {
	int T = (int)t.ops.size();
	if(x == 1) {
		dp[x] = 0;
	} else {
		dp[x] = t.get_min(v[x]) + sum[x] * v[x] + s[x];
	}
	t.add_line(line(-sum[x], dp[x]));
	for(pair<int, int> to : edges[x]) {
		if(to.first != p) {
			sum[to.first] = sum[x] + to.second;
			dfs(to.first, x);
		}
	}
	t.rollback(T);
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i = 0; i < n-1; ++i) {
		int u, v, w; cin >> u >> v >> w;
		edges[u].push_back({v, w});
		edges[v].push_back({u, w});
	}
	for(int i = 2; i <= n; ++i) {
		cin >> s[i] >> v[i];
	}
	dfs(1, 0);
	for(int i = 2; i <= n; ++i) {
		cout << dp[i] << ' ';
	}
}

Compilation message (stderr)

harbingers.cpp: In member function 'int lichao::add_line(long long int, long long int, line, int)':
harbingers.cpp:46:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |   ll m = l + r >> 1;
      |          ~~^~~
harbingers.cpp: In member function 'long long int lichao::get_min(long long int, long long int, long long int, int)':
harbingers.cpp:69:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |   ll m = l + r >> 1;
      |          ~~^~~

• Subtask 1: 0 / 100