Submission #314521

#	Time	Username	Problem	Language	Result	Execution time	Memory
314521		astoria	Harbingers (CEOI09_harbingers)	C++14	100 / 100	172 ms	32292 KiB

harbingers

#include "bits/stdc++.h"
using namespace std;
 
#define int long long
 
struct line{
	int m,c;
	int len_before;
};
 
const int N=1e5+5;
int n;
line rel[N];
vector<line> fake[N];
int dist[N];
vector<pair<int,int> > adj[N];
int dp[N];
int s[N],v[N];
int convhull_back;
 
void dfs_dist(int x, int pa){
	for(auto ii : adj[x]){
		if(ii.first==pa) continue;
		dist[ii.first] = dist[x] + ii.second;
		dfs_dist(ii.first,x);
	}
}
 
int f(int po, int x){
	return (rel[po].m*x)+rel[po].c;
}
 
int tern(int x){ //ternary search
	int lo = -1, hi = convhull_back;
	while (hi - lo > 1){
		int mid = (hi + lo)>>1;
		if (f(mid,x) < f(mid + 1,x)) 
			 hi = mid;
		else 
			 lo = mid; 
	}
	return f(lo+1,x);
}
 
double intersect(int m1, int c1, int m2, int c2){
	return (double)(c2-c1)/(m1-m2);
}
 
double intersect(line a, line b){
	return intersect(a.m,a.c,b.m,b.c);
}
 
int bin(line ne){
	int l=1, r=convhull_back; //first one that compares unfavourably to prev
	while(l<r){
		int m=(l+r)/2;
		if(intersect(rel[m],ne) <= intersect(rel[m-1],ne)) r=m;
		else l=m+1;
	}
	if(l==convhull_back){
		if(intersect(rel[l],ne)<=intersect(rel[l-1],ne)) return convhull_back;
		else return convhull_back+1;
	} 
	return l;
}
 
void dfs_ans(int x, int pa){
	int pos=0;
	if(pa==-1) goto ahc;
	//calc & insert
	dp[x] = tern(v[x]) + (v[x]*dist[x]) + s[x];
	line nl; nl.m = -dist[x]; nl.c = dp[x];
	nl.len_before = convhull_back;
	pos = bin(nl);
	convhull_back = pos;
	if(rel[pos].len_before==1e9){ //null value!
		rel[pos] = nl;
	}
	else{
		fake[pos].push_back(rel[pos]);
		rel[pos] = nl;
	}
 
	ahc: ;
	//dfs down
	for(auto ii : adj[x]){
		if(ii.first==pa) continue;
		dfs_ans(ii.first,x);
	}
	//delete
	convhull_back = rel[pos].len_before;
	if(!fake[pos].empty()){
		rel[pos] = fake[pos].back();
		fake[pos].pop_back();
	}
	else{
		rel[pos].len_before = 1e9; //null value!
	}
}
 
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin>>n;
	for(int i=0; i<n-1; i++){
		int u,v,w; cin>>u>>v>>w;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	}
	for(int i=2; i<=n; i++){ 
		cin>>s[i]>>v[i];
	}
	dfs_dist(1,-1);
	for(int i=0; i<=n; i++){ rel[i].len_before = -1e9;} //null value!
	dp[1] = 0; convhull_back = 0; 
	rel[0].m=0; rel[0].c=0; rel[0].len_before=-1;
	dfs_ans(1,-1);
	for(int i=2; i<=n; i++) cout<<dp[i]<<' ';
}

• Subtask 1: 100 / 100