Submission #842575

#	Time	Username	Problem	Language	Result	Execution time	Memory
842575		vjudge1	Harbingers (CEOI09_harbingers)	C++17	100 / 100	60 ms	20068 KiB

harbingers

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline bool _u(char x){return x>='0'&&x<='9';}
inline int read(){
	int x,f;
	char ch=getchar();
	for(f=1;!_u(ch);ch=='-'&&(f=-1),ch=getchar());
	for(x=0;_u(ch);x=(x<<1)+(x<<3)+(ch^48),ch=getchar());
	return x*f;
}
inline void write(int num){
	static int st[39],tp=0;
	num<0&&(putchar('-'),num=-num);
	do st[++tp]=num%10; while(num/=10);
	while(tp) putchar(st[tp--]|48);
	return;
}
const int N=1e5+10;
//dp[u]=s[u]+min(v[u]*(dep[u]-dep[f])+dp[f])
//dp[u]=s[u]+v[u]*dep[u]+min(dp[f]-v[u]*dep[f])
int dp[N],dep[N];
int st[N],tp;
int s[N],v[N];
vector<pair<int,int> > e[N];
inline bool check(int x,int y,int z){
	return (long double)(dp[y]-dp[x])*(dep[z]-dep[y])>(long double)(dp[z]-dp[y])*(dep[y]-dep[x]);
}
inline bool fyn(int x,int y,int z){
	return dp[x]-dp[y]<z*(dep[x]-dep[y]);
}
void dfs(int u,int f){
	#define MID(l,r) (((r-l)>>1)+l)
	if(tp){
		int l,r,mid;
		for(l=1,r=tp;l<r;){
			if(mid=MID(l,r),fyn(st[mid],st[mid+1],v[u])) r=mid;
			else l=mid+1;
		}
		dp[u]=s[u]+(dep[u]-dep[st[l]])*v[u]+dp[st[l]];
	}
	int l,r,mid;
	if(1<tp && !check(st[tp-1],st[tp],u)) r=tp;
	else
	for(l=1,r=tp;l<r;){
		if(mid=MID(l,r),check(st[mid],st[mid+1],u)) r=mid;
		else l=mid+1;
	}
	int fy=tp,ffy=st[tp=r+1];
	st[tp]=u;
	for(int i=0,to,val;i<e[u].size();++i){
		tie(to,val)=e[u][i];
		if(to!=f){
			dep[to]=dep[u]+val;
			dfs(to,u);
		}
	}
	st[tp]=ffy;
	tp=fy;
	#undef MID
}
int n;
signed main(){
//	freopen("har.in","r",stdin);
//	freopen("har.out","w",stdout);
	n=read();
	for(int i=1,u,v,w;i<n;++i)
		u=read(),v=read(),w=read(),e[u].emplace_back(v,w),e[v].emplace_back(u,w);
	for(int i=2;i<=n;++i)
		s[i]=read(),v[i]=read();
	dfs(1,0);
	for(int i=2;i<=n;++i) write(dp[i]),putchar(i==n?'\n':' ');
	return(0-0);
}
/*
5
1 2 20
2 3 12
2 4 1
4 5 3
26 9
1 10
500 2
2 30

*/

Compilation message (stderr)

harbingers.cpp: In function 'void write(long long int)':
harbingers.cpp:14:26: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   14 |  num<0&&(putchar('-'),num=-num);
      |                       ~~~^~~~~
harbingers.cpp: In function 'void dfs(long long int, long long int)':
harbingers.cpp:51:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i=0,to,val;i<e[u].size();++i){
      |                     ~^~~~~~~~~~~~

• Subtask 1: 100 / 100