Submission #842654

#	Time	Username	Problem	Language	Result	Execution time	Memory
842654		vjudge1	Harbingers (CEOI09_harbingers)	C++17	50 / 100	58 ms	16396 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 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]);
}

inline pair<int,int> slove(int u,bool flag,pair<int,int>fy={0,0}){
	#define MID(l,r) (((r-l)>>1)+l) 
	static int st[N],tp=0,kk=0;
	if(!kk) memset(st,0,sizeof st);
	kk=1;
	if(flag){
		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;
		return make_pair(fy,ffy);
	}else{
		st[tp]=fy.first;
		tp=fy.second;
		return make_pair(114514,119810);
	}
	#undef MID
}
int now[N],fa[N];
pair<int,int>ffy[N];
void dfs(){
	static int st[N],tp=0;
	st[++tp]=1;
	for(int to,val;tp;){
		int u=st[tp];
		if(now[u]==(int)e[u].size()){
			slove(u,0,ffy[u]);
			--tp;
			continue;
		}
		if(!now[u]) ffy[u]=slove(u,1);
		tie(to,val)=e[u][now[u]++];
		if(to==fa[u])continue;
		dep[to]=dep[u]+val,fa[to]=u;
		st[++tp]=to;
	}
}
int n;
signed main(){
	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();
	for(int i=2;i<=n;++i) write(dp[i]),putchar(i==n?'\n':' ');
	return(0-0);
}

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);
      |                       ~~~^~~~~

• Subtask 1: 50 / 100