Submission #871140

#	Time	Username	Problem	Language	Result	Execution time	Memory
871140		Saul0906	Harbingers (CEOI09_harbingers)	C++14	70 / 100	187 ms	65536 KiB

harbingers

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<ll, ll>
#define ll long long
#define ld long double
#define rep(a,b,c) for(int a=b; a<c; a++) 
#define repa(a,b) for(auto a: b)

using namespace std;

const int lim=1e5+5;
vector<pii> ady[lim];
bool vis[lim]{};
pii harb[lim];
ll dp[lim]{};
ll dis=0;

struct line{
	ll m, b;
};

ll eval(line a, ll x){
	return (dis+a.m)*x+a.b;
}

ld isec(line l1, line l2){
	return (ld)(l1.b-l2.b)/(l2.m-l1.m);
}

deque<line> cht;
vector<line> deleted[lim];

ll solve(int u){
	ll l=0, r=cht.size()-1, mid, x=(ll)harb[u].se;
	while(l<=r){
		mid=(l+r)/2;
		if(mid==cht.size()-1 || isec(cht[mid],cht[mid+1])>=(ld)x) r=mid-1;
		else l=mid+1;
	}
	return eval(cht[l],x)+(ll)harb[u].fi;
}

void dfs(int u){
	vis[u]=true;
	if(u>1) dp[u]=solve(u);
	cht.push_back({-dis,dp[u]});
	int sz=cht.size();
	while(sz>2 && isec(cht[sz-1],cht[sz-2])<=isec(cht[sz-1],cht[sz-3])){
		//cout<<isec(cht[sz-1],cht[sz-2])<<endl;
		deleted[u].push_back(cht[sz-2]);
		cht[sz-2]=cht[sz-1];
		cht.pop_back();
		sz--;
	}
	repa(v, ady[u]){
		if(!vis[v.fi]){
			dis+=v.se;
			dfs(v.fi);
			dis-=v.se;
		}
	}
	cht.pop_back();
	while(deleted[u].size()){
		cht.push_back(deleted[u].back());
		deleted[u].pop_back();
	}
}

int main(){
	ll u, v, w;
	int n;
	cin>>n;
	rep(i,1,n){
		cin>>u>>v>>w;
		ady[u].push_back({v,w});
		ady[v].push_back({u,w});
	}
	rep(i,2,n+1) cin>>harb[i].fi>>harb[i].se;
	dfs(1);
	rep(i,2,n+1) cout<<dp[i]<<" ";
	cout<<endl;
}

Compilation message (stderr)

harbingers.cpp: In function 'long long int solve(int)':
harbingers.cpp:38:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   if(mid==cht.size()-1 || isec(cht[mid],cht[mid+1])>=(ld)x) r=mid-1;
      |      ~~~^~~~~~~~~~~~~~

• Subtask 1: 70 / 100