Submission #571760

#	Time	Username	Problem	Language	Result	Execution time	Memory
571760		Blagojce	Harbingers (CEOI09_harbingers)	C++11	10 / 100	143 ms	65536 KiB

harbingers

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define st first
#define nd second 
#define all(x) begin(x), end(x)
#define pb push_back
#define all(x) begin(x), end(x)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const int mxn = 2e5+5;
const ll inf = 1e18;
const ld eps = 1e-13;
mt19937 _rand(time(0));


struct line{
        ll m, b;
        bool isq;
        ll x;
	ll eval(ll X) const{
                return X * m + b;
        }
	ll intersect(const line &l) const{
                return (l.b - b) / (m - l.m);
        }
        bool operator < (const line &l) const{
                if(l.isq) return x < l.x;
                else return m > l.m;
        }
};
set<line> hull;
set<line> hull2[mxn];
typedef set<line>::iterator iter;
bool cPrev(iter it){
        return it != hull.begin();
}
bool cNext(iter it){
        return it != hull.end() && next(it) != hull.end();
}
bool bad(const line &l1, const line &l2, const line &l3){
        return l1.intersect(l3) <= l1.intersect(l2);
}
bool bad(iter it){
        return cPrev(it) && cNext(it) && bad(*prev(it), *it, *next(it));
}

iter update(iter it){
        if(!cPrev(it)) return it;
        ll x = prev(it)->intersect(*it);
        line l = *it;
        l.x = x;
        it = hull.erase(it);
        return hull.insert(it, l);

}
void addLine(ll m, ll b){
        line l;
        l.m = m, l.b = b, l.isq = false;
        l.x = -inf;
        iter it = hull.lower_bound(l);

        it = hull.insert(it, l);
        if(bad(it)){
                hull.erase(it);
                return;
        }
        while(cPrev(it) && bad(prev(it))) hull.erase(prev(it));
        while(cNext(it) && bad(next(it))) hull.erase(next(it));
        it = update(it);
        if(cPrev(it)) update(prev(it));
        if(cNext(it)) update(next(it));
}
ll query(ll x){
        line q;
        q.x = x;
        q.isq = true;
        iter it = --hull.lower_bound(q);
    
        ll  ret = it->eval(x);

        return ret;
}









int n;
vector<pii> g[mxn];
ll ans[mxn];
ll s[mxn], v[mxn];



void dfs(int u, int p, ll dep){
	if(u != p){
		hull = hull2[p];
		ans[u] = s[u] + v[u]*dep + query(v[u]);
		addLine(-dep, ans[u]);
		hull2[u] = hull;
	}
	for(auto e : g[u]){
		if(e.st == p) continue;
		dfs(e.st, u, dep + e.nd);
	}
}





int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	fr(i, 0, n-1){
		int u, v, w;
		cin >> u >> v >> w;
		--u, --v;
		g[u].pb({v, w});
		g[v].pb({u, w});
	}
	fr(i, 1, n){
		cin >> s[i] >> v[i];
	}
	
	addLine(0, 0);
	hull2[0] = hull;
	
	dfs(0, 0, 0);
	fr(i, 1, n) cout<<ans[i]<<' ';
	cout<<endl;
	return 0;
}/*
1
3
2 3 -1*/

• Subtask 1: 10 / 100