Submission #1190561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190561		g4yuhg	Harbingers (CEOI09_harbingers)	C++20	100 / 100	65 ms	24488 KiB

harbingers

//Huyduocdithitp
#include <bits/stdc++.h>
typedef long long ll;
#define endl '\n'
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define fi first
#define se second
#define pii pair<ll, ll>
#define inf 1e18
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MP make_pair
#define TASK "ghuy4g"
#define start if(fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define LOG 19
#define N 300010
using namespace std;
struct op {
	ll pos, top;
	pii ov;// cai doan bi ghi de
};
ll n;
vector<pii> adj[N];
ll S[N], V[N];
pii lines[N];
vector<op> undo;
ll top;
bool bad(pii a, pii b, pii c) {
    return (double)(b.se - a.se) / (a.fi - b.fi) >= (double)(c.se - a.se) / (a.fi - c.fi);
}
ll cal(pii u, ll x) {
	return u.fi * x + u.se;
}
ll get(ll x) {
	ll l = 0, r = top - 2, ans = cal(lines[l], x);
	while (l <= r) {
		ll mid = (l + r) / 2;
		ll X = cal(lines[mid], x);
		ll Y = cal(lines[mid + 1], x);
		if (X > Y) {
			l = mid + 1;
		}
		else {
			r = mid - 1;
		}
		ans = min(ans, min(X, Y));
	}
	/*while (l < r) {
		ll mid = (l + r) / 2;
		ll X = cal(lines[mid], x);
		ll Y = cal(lines[mid + 1], x);
		if (X > Y) {
			l = mid + 1;
		}
		else {
			r = mid;
		}
		ans = min(ans, min(X, Y));
	}*/
	return ans;
}
void inLine(pii newLine) {
	ll l = 1, r = top - 1, k = top; // neu khong tim dc vi tri bad=>top
	while (l <= r) {
		ll mid = (l + r) / 2;
		if (bad(lines[mid - 1], lines[mid], newLine)) {
			k = mid;
			r = mid - 1;
		}
		else {
			l = mid + 1;
		}
	}
	undo.push_back({k, top, lines[k]});
	top = k + 1;
	lines[k] = newLine;
	//cout << top << " " << k << endl;
}
void lui() {
	op xet = undo.back(); undo.pop_back();
	top = xet.top; lines[xet.pos] = xet.ov;
	//cout << "lui " << top << " " << xet.pos << endl;
}
ll d[N], f[N];
void dfs(ll u, ll parent) {
	if (u != 1) {
		f[u] = get(V[u]) + S[u] + V[u] * d[u];
	}
	inLine({-d[u], f[u]});
	for (auto v : adj[u]) {
		if (v.fi == parent) continue;
		d[v.fi] = d[u] + v.se;
		dfs(v.fi, u);
	}
	lui();
}
signed main(void) {
    faster;	
    cin >> n;
    for (int i = 1; i <= n - 1; i ++) {
    	ll u, v, w;
    	cin >> u >> v >> w;
    	adj[u].push_back({v, w});
    	adj[v].push_back({u, w});
    }
	for (int i = 2; i <= n; i ++) {
		cin >> S[i] >> V[i];
	}    
	dfs(1, 1);
	for (int i = 2; i <= n; i ++) {
		cout << f[i] << " ";
	}
    return 0;
}

• Subtask 1: 100 / 100