Submission #868230

#	Time	Username	Problem	Language	Result	Execution time	Memory
868230		Saul0906	Harbingers (CEOI09_harbingers)	C++14	70 / 100	117 ms	23376 KiB

harbingers

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

using namespace std;

const ll inf=2e18;
ll dis=0;
int cont=0;
struct line{
	ll m=1e9, b=1e9;
	int id=0;
	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;
	}
};

const int lim=1e5+5;
line deleted[lim]{};
int n;
vector<pii> ady[lim];
pii harb[lim];
bool vis[lim]{};
ll dp[lim]{};
ifstream in;
ofstream out;
ll h=0;

struct lichao{
	lichao *left=0, *right=0;
	ll l, r, mid;
	line act;
	lichao(ll x, ll y){
		l=x;
		r=y;
		mid=(l+r)/2ll;
	}
	void insert(line nw){
		if(!act.ex){
			act=nw;
			return;
		}
		if((l==r || act.m==nw.m) && act.eval(mid)>nw.eval(mid)) return;
		if(act.eval(mid)>nw.eval(mid)) swap(act,nw);
		if(l==r || act.m==nw.m){
			deleted[act.id]=nw;
			return;
		}
		if(act.m<nw.m){
			if(!left) left=new lichao(l,mid);
			left->insert(nw);
		}else{
			if(!right) right=new lichao(mid+1ll,r);
			right->insert(nw);
		}
	}
	ll query(ll x){
		if(r<x || x<l) return inf;
		while(act.ex && !vis[act.id]) act=deleted[act.id];
		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;
	}
};

lichao cht(0,2e9);

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

int main(){
	in.open("harbingers.in");
	out.open("harbingers.out");
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	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]<<" ";
	}
}

• Subtask 1: 70 / 100