Submission #866331

#	Time	Username	Problem	Language	Result	Execution time	Memory
866331		Saul0906	Harbingers (CEOI09_harbingers)	C++17	0 / 100	2 ms	4956 KiB

harbingers

#include <bits/stdc++.h>
#define cin in
#define cout out
#define ll long long int
#define pii pair<ll, ll>
#define fi first
#define se second

using namespace std;

const ll inf=2e18;
ll dis=0;

struct line{
	ll m, b;
	bool ex=false;
	ll eval(ll x){
		return (dis+m)*x+b;
	}
	bool operator==(line a)const{
		return m==a.m && b==a.b && ex==a.ex;
	}
};

struct lichao{
	lichao *left, *right;
	int l, r, mid;
	line act;
	lichao(int x, int y){
		l=x;
		r=y;
		mid=(l+r)/2;
	}
	void insert(line nw){
		if(act.ex){
			if(act.eval(mid)>nw.eval(mid)){
				swap(act,nw);
			}
			if(l==r) return;
			if(act.m<nw.m){
				if(!left) left=new lichao(l,mid);
				left->insert(nw);
			}else{
				if(!right) right=new lichao(mid+1,r);
				right->insert(nw);
			}
			return;
		}
		act=nw;
	}
	void erase(line nw){
		if(act==nw){
			act.ex=false;
			return;
		}
		if(act.m<nw.m && left) left->erase(nw);
		else if(right) right->erase(nw);
	}
	ll query(ll x){
		if(r<x || x<l) return inf;
		if(l==r){
			if(act.ex) return act.eval(x);
			else return inf;
		}
		ll ans=inf;
		if(act.ex) ans=act.eval(x);
		if(left) ans=min(ans,left->query(x));
		if(right) ans=min(ans,right->query(x));
		return ans;
	}
};

int n;
const int lim=1e5+5;
vector<pii> ady[lim];
pii harb[lim];
bool vis[lim]{};
ll dp[lim]{};
lichao cht(2,lim);

void dfs(int u, ll h=0){
	line act;
	vis[u]=true;
	if(u>1){
		dis=h;
		dp[u]=harb[u].fi+cht.query(harb[u].se);
	}
	act={-h,dp[u],true};
	cht.insert(act);
	for(auto v:ady[u]){
		if(!vis[v.fi]){
			dfs(v.fi,h+v.se);
		}
	}
	cht.erase(act);
}

int main(){
	ifstream in;
	ofstream out;
	in.open("harbingers.in");
	out.open("harbingers.out");
	int u, v;
	ll w;
	int n;
	cin>>n;
	for(int i=1; i<n; i++){
		cin>>u>>v>>w;
		ady[u].push_back({v,w});
		ady[v].push_back({u,w});
	}
	for(int i=2; i<=n; i++){
		cin>>harb[i].fi>>harb[i].se;
	}
	dfs(1);
	for(int i=2; i<=n; i++) cout<<dp[i]<<" ";
	cout<<endl;
}

• Subtask 1: 0 / 100