제출 #926413

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
926413		Karoot	Harbingers (CEOI09_harbingers)	C++17	30 / 100	96 ms	65536 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){
		if (empty())return false;
		auto it = lower_bound({k, m, -1});
		if (it == end())return false;
		if ((*it).k == k && (*it).m == m){
			erase(it);
			return true;
		}
		return false;
	}
};

const int MAXN = 1e5+4;

LineContainer LC;


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

ll dp[MAXN];


void buildTree(ll node, ll parent, ll w, ll de){
	d[node] = w;
	//cout << "check" << " ";
	//cout << adj[node].size() << endl;	
	for (auto& p : adj[node]){
		if (p.first != parent){
			children[node].push_back(p.first);
			buildTree(p.first, node, w+p.second, de+1);
		}
	}
	return;
}


void dfs(ll node){
	if (node == 0){
		dp[node] = 0;
	} else {
		dp[node] = -LC.query(w[node]) + s[node] + d[node]*w[node];
	}


	LineContainer LC1 = LC;
	LC.add(d[node], -dp[node]);


	for (ll x : children[node]){
		dfs(x);
	}

	LC = LC1;

	//cout << node << ": " << endl;
}


int main(){
    scoobydoobydoo();
	//freopen("har.in", "r", stdin);
	//freopen("har.ans", "w", stdout);
	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});
		dp[i+1] = 0; 
	}

	//cout << "cool" << endl;

	buildTree(0, 0, 0, 0);

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

	//cout << 1 << endl;

	dfs(0);


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

	//cout << d[1] << endl;


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






    return 0;
}

• Subtask 1: 30 / 100