Submission #926297

#	Time	Username	Problem	Language	Result	Execution time	Memory
926297		Karoot	Harbingers (CEOI09_harbingers)	C++17	50 / 100	89 ms	25428 KiB

harbingers

#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
#include <climits>

#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()

using namespace std;

typedef long long ll;

ll linf = 1e15+1;

inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}

struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	ll query(ll x) {
		if (empty())return linf;
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
	bool eras(ll k, ll m){
		auto it = find({k, m, 0});
		if ((*it).k == k && (*it).m == m){
			erase(it);
			return true;
		}
		return false;
	}
};

const int MAXN = 1e5+4;

LineContainer LC;


vector<int> children[MAXN];
ll d[MAXN];
vector<pair<int, int>> adj[MAXN];
ll w[MAXN], s[MAXN];

ll dp[MAXN];

void buildTree(int node, int parent, ll w){
	d[node] = w;
	for (auto p : adj[node]){
		if (p.first != parent){
			children[node].push_back(p.first);
			buildTree(p.first, node, w+p.second);
		}
	}
}


void dfs(int node){
	if (node == 0){
		dp[node] = 0;
	} else {
		dp[node] = -LC.query(w[node]) + s[node] + d[node]*w[node];
	}
	
	for (int x : children[node]){
		LC.add(d[node], -dp[node]);
		dfs(x);
	}
	//cout << node << ": " << endl;
	LC.eras(d[node], -dp[node]);
}


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

	buildTree(0, 0, 0);

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

	dfs(0);

	//for (int i = 0; i < n; i++)cout << i << ": " << d[i] << endl;


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





    return 0;
}

• Subtask 1: 50 / 100