Submission #937191

#	Time	Username	Problem	Language	Result	Execution time	Memory
937191		amirhoseinfar1385	Harbingers (CEOI09_harbingers)	C++17	100 / 100	141 ms	27204 KiB

harbingers

//#pragma GCC optimize("O3,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
long long inf=1e18,kaf=(1<<16),sor,makh;
struct func{
	func(){
		fas=shib=0;
	}
	long long fas;
	int shib;
	int inersect(func f){
		sor=fas-f.fas,makh=f.shib-shib;
		if(makh==0){
			if(sor>0){
				return -1;
			}
			return inf;
		}
		if(makh<0){
			makh*=-1;
			sor*=-1;
		}
		if(sor<0){
			return -1;
		}
		return min((sor+makh-1)/makh,1000000000ll+3);
	}
	bool operator <(const func f)const {
		return shib<f.shib;
	}
}fakefunc,fp[maxn];
int p;
long long taf;
struct cht{
	vector<pair<int,int>>st;
	void add(int f){
		while((int)st.size()>0){
			taf=fp[f].inersect(fp[st.back().second]);
			if(taf>1e9+10){
				return ;
			}
			if(taf<=st.back().first){
				st.pop_back();
				continue;
			}else{
				st.emplace_back(make_pair(taf,f));
				break;
			}
		}
		if((int)st.size()==0){
			st.emplace_back(make_pair(-1,f));
		}
	}
	long long get(int x){
		p=lower_bound(st.begin(),st.end(),make_pair(x+1,1))-st.begin()-1;
		if(p<0){
			return -inf;
		}
		return (fp[st[p].second]).fas+1ll*x*(fp[st[p].second]).shib;
	}
};
long long ret;
int m;

struct segment{
	cht ch[(1<<17)];
	void upd(int i,int l,int r,int tl,int tr,int u){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			ch[i].add(u);
			return ;
		}
		m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,u);
		m=(l+r)>>1;
		upd((i<<1)^1,m+1,r,tl,tr,u);
	}
	void pors(int x,int v){
		ret=-inf;
		x+=kaf;
		while(x>0){
			ret=max(ret,ch[x].get(v));
			x>>=1;
		}
	}
	void clear(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			ch[i].st.clear();
			ch[i].st.shrink_to_fit();
			return ;
		}
		m=(l+r)>>1;
		clear((i<<1),l,m,tl,tr);
		m=(l+r)>>1;
		clear((i<<1)^1,m+1,r,tl,tr);
	}
}seg;

struct yal{
	int u,v,w;
	int getad(int fu){
		return (u^v^fu);
	}
}alle[maxn];
int n,timea=-1,high[maxn];
long long dp[maxn];
pair<int,int>stf[maxn],all[maxn];
vector<int>adj[maxn];

void dfs(int u,int par=0,int len=0){
	if((int)adj[u].size()==1&&u!=1){
		timea++;
		stf[u].first=timea;
	}else{
		stf[u].first=timea+1;
	}
	high[u]=len;
	for(auto x:adj[u]){
		int v=alle[x].getad(u);
		if(v!=par){
			dfs(v,u,len+alle[x].w);
		}
	}
	stf[u].second=timea;
}

void vorod(){
	cin>>n;
	for(int i=0;i<n-1;i++){
		cin>>alle[i].u>>alle[i].v>>alle[i].w;
		adj[alle[i].u].push_back(i);
		adj[alle[i].v].push_back(i);
	}
	for(int i=2;i<=n;i++){
		cin>>all[i].first>>all[i].second;
	}
}

void pre(){
	dfs(1);
}

void upd(int u){
	seg.pors(stf[u].first,all[u].second);
	dp[u]=1ll*min(-ret,0ll)+all[u].first+1ll*all[u].second*high[u];
	fp[u].fas=-dp[u];
	fp[u].shib=high[u];
	seg.upd(1,0,kaf-1,stf[u].first,stf[u].second,u);
}

void solve(int u=1,int para=0){
	upd(u);
	for(auto x:adj[u]){
		int v=alle[x].getad(u);
		if(v!=para){
			solve(v,u);
		}
	}
	seg.clear(1,0,kaf-1,stf[u].first,stf[u].second);
}

void khor(){
	for(int i=2;i<=n;i++){
		cout<<dp[i]<<" ";
	}
	cout<<"\n";
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	vorod();
	pre();
	solve();
	khor();
}

• Subtask 1: 100 / 100