Submission #1156732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156732		nikolashami	Harbingers (CEOI09_harbingers)	C++20	10 / 100	2 ms	2884 KiB

harbingers

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

const ll N=2.5e3+4;
vector<array<int,2>>g[N];
ll S[N],V[N],D[N],P[N],F[N],n;

struct Line{
	ll k=0,nn=0,ac=0;
	ll f(ll x){return(k*x)+nn;}
};
 
struct Pers_Li_Chao{
	vector<Line>st;
	vector<ll>lc,rc,root;
	ll nn,nd;
	void ch(ll sz){
		nn=sz;
		nd=1;
		st.clear();
		lc.clear();
		rc.clear();
		root.clear();
		st.resize(21*sz+5);
		lc.resize(21*sz+5);
		rc.resize(21*sz+5);
		root.resize(5+sz);
		root[0]=1;
	}
	ll nw(){return++nd;}
	void build(ll i=1,ll l=1,ll r=n){
		if(l==r)return;
		lc[i]=nw();
		rc[i]=nw();
		build(lc[i],l,(l+r)/2);
		build(rc[i],(l+r)/2+1,r);
	}
	void add(Line L,ll tr,ll pr,ll l=1,ll r=-1){
		if(r==-1)r=nn; 
		st[tr]=st[pr];
		if(!st[tr].ac){st[tr]=L;return;}
		ll md=(l+r)/2;
		if(st[tr].f(P[r])<L.f(P[r])&&st[tr].f(P[l])<L.f(P[l]))return;
		if(st[tr].f(P[l])>=L.f(P[l])&&st[tr].f(P[r])>=L.f(P[r])){st[tr]=L;return;}
		if(L.f(P[l])<=st[tr].f(P[l]))swap(L,st[tr]);
		if(L.f(P[md])<st[tr].f(P[md])){
			rc[tr]=rc[pr];
			lc[tr]=nw();
			add(st[tr],lc[tr],lc[pr],l,md);
			st[tr]=L;
		}else{
			lc[tr]=lc[pr];
			rc[tr]=nw();
			add(L,rc[tr],rc[pr],md+1,r);
		}
	}
	ll get(ll X,ll i,ll l=1,ll r=-1){
		if(r==-1)r=nn;
		if(!st[i].ac)return 0;
		if(l==r)return st[i].f(X);
		ll md=(l+r)/2,ret=st[i].f(X);
		if(X<=P[md])ret=min(ret,get(X,lc[i],l,md));
		else ret=min(ret,get(X,rc[i],md+1,r));
		return ret;
	}
	void reset(){
		for(int i=0;i<st.size();++i)
			st[i].k=st[i].nn=st[i].ac=0;
	}
}C;

void QG(ll u,ll p){
	for(auto[v,w]:g[u]){
		if(v==p)continue;
		D[v]=D[u]+w;
		QG(v,u);
	}
}

void dfs(ll u,ll p){
	F[u]=S[u]+D[u]*V[u]+C.get(V[u],C.root[p]);
	C.root[u]=C.nw();
	C.add({-D[u],F[u],1},C.root[u],C.root[p]);
	for(auto[v,w]:g[u])
		if(v^p)dfs(v,u);
	C.root[u]=C.root[p];
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>n;
    for(int i=1,u,v,w;i<n;++i){
    	cin>>u>>v>>w;
    	g[u].push_back({v,w});
    	g[v].push_back({u,w});
    }

    for(int i=2;i<=n;++i){
    	cin>>S[i]>>V[i];
    	P[i]=V[i];
    }

    sort(P+1,P+n+1);

    C.ch(n);
    C.build();

    QG(1,0);
    dfs(1,0);

    for(int i=2;i<=n;++i)
    	cout<<F[i]<<' ';
}

• Subtask 1: 10 / 100