Submission #641896

#	Time	Username	Problem	Language	Result	Execution time	Memory
641896		itnes	Harbingers (CEOI09_harbingers)	C++14	20 / 100	1097 ms	65536 KiB

harbingers

#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<int,int> pii;
const ll INFLL=1e18+7;
const int INF=1e9+7;
#define pb push_back
struct line{
	ll a,b;
	ll operator()(ll x){return a*x+b;}
};
struct node{
	node *left_node=nullptr,*right_node=nullptr;
	line l;
	node(line x){l=x;}
};
struct rollback{
	int idx;
	node *where;
	bool side;
	line pre_val;
	bool oper_type;
	void make_rollback(){
		if(oper_type){
			if(!side){
				delete where->left_node;
				where->left_node=nullptr;
			}else{
				delete where->right_node;
				where->right_node=nullptr;
			}
		}else{
			where->l=pre_val;
		}
	}
};
int curr;
vector<rollback> rollbacks;
void update(node *v,int start,int end,line x){
	if(v->l(start)<x(start)&&v->l(end)<x(end)) return;
	if(v->l(start)>x(start)&&v->l(end)>x(end)){rollbacks.pb({curr,v,0,v->l,0}); v->l=x; return;}
	int mid=(start+end)>>1;
	if(v->l(mid)>x(mid)){
		rollbacks.pb({curr,v,0,v->l,0});
		swap(v->l,x);
	}
	if(v->l(start)>x(start)){
		if(v->left_node==nullptr){rollbacks.pb({curr,v,0,{0,0},1}); v->left_node=new node(x);}
		else update(v->left_node,start,mid,x);
	}else{
		if(v->right_node==nullptr){rollbacks.pb({curr,v,1,{0,0},1}); v->right_node=new node(x);}
		else update(v->right_node,mid+1,end,x);
	}
}
ll query(node *v,int start,int end,int x){
	if(v==nullptr) return INFLL*5;
	if(start==end) return v->l(x);
	int mid=(start+end)>>1;
	if(x<=mid) return min(v->l(x),query(v->left_node,start,mid,x));
	else return min(v->l(x),query(v->right_node,mid+1,end,x));
}
node *root=new node({0,0});
void update(line x){++curr; update(root,-INF,INF,x);}
ll query(ll x){return query(root,-INF,INF,x);}
const int MAXN=1e5+7;
line arr[MAXN];
vector<pii> G[MAXN];
ll depth[MAXN];
ll dp[MAXN];
int preorder[MAXN];
int idx;
void DFS(int x,int pre,int dist){
	preorder[x]=++idx;
	depth[x]=depth[pre]+dist;
	//enter
	if(x!=1){
		ll tmp=arr[x].b+arr[x].a*depth[x];
		tmp+=query(arr[x].a);
		dp[x]=tmp;
		update({-depth[x],dp[x]});
	}
	for(pii v:G[x]) if(v.first!=pre) DFS(v.first,x,v.second);
	//exit
	if(x!=1){
		while(!rollbacks.empty()&&rollbacks.back().idx==preorder[x]-1){
			rollbacks.back().make_rollback();
			rollbacks.pop_back();
		}
		rollbacks.shrink_to_fit();
	}
}
int main()
{
	ios_base::sync_with_stdio(0);
	int n; cin>>n;
	for(int i=1;i<n;++i){
		int a,b,c; cin>>a>>b>>c;
		G[a].pb({b,c});
		G[b].pb({a,c});
	}
	for(int i=2;i<=n;++i){
		int a,b; cin>>a>>b;
		arr[i]={b,a};
	}
	DFS(1,1,0);
	for(int i=2;i<=n;++i) cout<<dp[i]<<" ";
	cout<<'\n';
}

• Subtask 1: 20 / 100