Submission #944257

#	Time	Username	Problem	Language	Result	Execution time	Memory
944257		phoenix0423	Harbingers (CEOI09_harbingers)	C++17	20 / 100	103 ms	65536 KiB

harbingers

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int INF = 1e9 + 7;
const int maxn = 2e5 + 5;
vector<pll> adj[maxn];
int a[maxn], b[maxn], ans[maxn];
int n;
struct LiChaoTree{
	struct seg{
		int m, k;
		seg(){}
		seg(int _m, int _k) : m(_m), k(_k){}
		int operator ()(int x){
			return m * x + k;
		}
	};
	struct node{
		node *l, *r;
		seg ans;
		node() : l(nullptr), r(nullptr), ans(seg(0, 0)){}
		node(int m, int k) : l(nullptr), r(nullptr), ans(seg(m, k)){} 
		node(seg _ans) : l(nullptr), r(nullptr), ans(_ans){}
		node(node *nd) : l(nd->l), r(nd->r), ans(nd->ans){}
	} *rt;
	void insert(seg cur, node *&nd, int l, int r){
		if(!nd){
			nd = new node(cur);
			return;
		}
		nd = new node(nd);
		if(l == r){
			if(nd->ans(l) > cur(l)) swap(nd->ans, cur);
			return;
		}
		int m = (l + r) / 2;
		if(nd->ans(m) > cur(m)) swap(nd->ans, cur);
		if(nd->ans.m < cur.m) insert(cur, nd->l, l, m);
		else insert(cur, nd->r, m + 1, r);
	}
	void insert(int m, int k){ insert(seg(m, k), rt, 0, INF);}
	int qry(int pos, node *nd, int l, int r){
		if(!nd) return INF * INF;
		if(l == r) return nd->ans(pos);
		int m = (l + r) / 2;
		if(pos <= m) return min(nd->ans(pos), qry(pos, nd->l, l, m));
		else return min(nd->ans(pos), qry(pos, nd->r, m + 1, r));
	}
	int qry(int pos){ return qry(pos, rt, 0, INF);}

} st[maxn];

int dep[maxn];

void dfs(int pos, int prev){
	if(pos){
		ans[pos] = a[pos] + b[pos] * dep[pos] + st[prev].qry(b[pos]);
	}
	st[pos].rt = st[prev].rt;
	st[pos].insert(-dep[pos], ans[pos]);
	for(auto [x, w] : adj[pos]){
		if(x == prev) continue;
		dep[x] = dep[pos] + w;
		dfs(x, pos);
	}
}

signed main(void){
	fastio;
	cin>>n;
	for(int i = 0; i < n - 1; i++){
		int a, b, w;
		cin>>a>>b>>w;
		a--, b--;
		adj[a].eb(b, w);
		adj[b].eb(a, w);
	}
	for(int i = 1; i < n; i++){
		cin>>a[i]>>b[i];
	}
	dfs(0, -1);
	for(int i = 1; i < n; i++) cout<<ans[i]<<" ";
	cout<<"\n";
}

• Subtask 1: 20 / 100