Submission #1361467

#	Time	Username	Problem	Language	Result	Execution time	Memory
1361467		man	Harbingers (CEOI09_harbingers)	C++17	70 / 100	1096 ms	25140 KiB

harbingers

/// Day Created: apr 29th 2026
#include <iostream>
#include <algorithm>
#include <vector>

#define fname "."
#define ll long long
#define pii pair<int, int>
#define pil pair<int, ll>
#define fi first
#define se second

using namespace std;
int n;
vector<pii> edge[100005];
int S[100005], V[100005];
ll f[100005], pref[100005];

struct CHT {
	vector<pil> lines, history;
	int sz, until[100005];

	void rollback(int until) {
		while((int)history.size()>until) {
			if(history.back().fi==-1) 
				lines.pop_back(), --sz;
			else lines.emplace_back(history.back()), ++sz;
			history.pop_back();
		}
	}

	void update(int a, ll b, const int &v) { // (b2-b1)/(a1-a2)>=(b3-b2)/(a2-a3)
		while(sz>=2 && 1.0*(lines[sz-1].se-lines[sz-2].se)/(lines[sz-2].fi-lines[sz-1].fi)>=1.0*(b-lines[sz-1].se)/(lines[sz-1].fi-a)) {
			history.emplace_back(lines.back());
			lines.pop_back(), 
			--sz;
		}
		lines.emplace_back(a, b);
		++sz;
		history.emplace_back(-1, 0);
		until[v]=(int)history.size();
	}

	ll get(int x) {
		int res=0;
		int l=0, r=sz-1;
		while(l<r) {
			int m=(l+r)>>1;
			if(m+1<sz) 
				(1ll*lines[m].fi*x+lines[m].se>=1ll*lines[m+1].fi*x+lines[m+1].se)?(l=m+1, res=l):(r=m, res=r);
			else {
				res=m;
				break;
			}
		}
		return 1ll*lines[res].fi*x+lines[res].se;
	}
} *cht;

// f[i]=f[j]+s[i]+(pref[i]-pref[j])*v[i]
// f[i]=-pref[j]*v[i]+f[j]  +s[i]+pref[i]*v[i]

void dfs(int u, int par) {
	for(const auto &[v, d]:edge[u]) 
		if(v!=par) {
			pref[v]=pref[u]+d;
			if(cht->sz==0) f[v]=pref[v]*V[v]+S[v];
			else f[v]=min(0ll, cht->get(V[v]))+pref[v]*V[v]+S[v];
			cht->update(-pref[v], f[v], v);
			dfs(v, u);
			cht->rollback(cht->until[u]);
		}
}

main() {
	if(fopen(fname"inp", "r")) {
		freopen(fname"inp", "r", stdin);
		freopen(fname"out", "w", stdout);
	}
	cin.tie(0)->sync_with_stdio(0);
	cin>>n;
	for(int i=1; i<n; ++i) {
		int u, v, d;
		cin>>u>>v>>d;
		edge[u].emplace_back(v, d);
		edge[v].emplace_back(u, d);
	}
	for(int i=2; i<=n; ++i) cin>>S[i]>>V[i];
	cht=new CHT();
	dfs(1, 0);
	for(int i=2; i<=n; ++i) cout<<f[i]<<' ';

	delete cht;
}

Compilation message (stderr)

harbingers.cpp:75:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   75 | main() {
      | ^~~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:77:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |                 freopen(fname"inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:78:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |                 freopen(fname"out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 70 / 100