Submission #1249018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249018		_rain_	Harbingers (CEOI09_harbingers)	C++20	100 / 100	118 ms	30136 KiB

harbingers

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = (int)3e5;

struct Line {
	LL a,b;
	Line (LL a = 0,LL b = LLONG_MAX) : a(a) , b(b) {};
	LL F(LL x){
		return a*x + b;
	}
};

struct State{
	int size;
	int add_pos;
	Line val;
};

struct CHT{
	public:
		long double get_intersec(Line x,Line y){
			return (long double)(y.b - x.b) / (x.a - y.a);
		}
		vector<Line> line;
		vector<State> order;
		int cur_size = 0;
		
		void reload_size(int n){
			line = vector<Line>(n+3,Line());
			cur_size = 0;
			return;
		}
		
		void add_line(Line x){
			int low = 1 , high = cur_size - 1;
			int pos = cur_size;
			
			while (low<=high){
				int mid = (low+high)/2;
				if (get_intersec(line[mid - 1] , line[mid]) >= get_intersec(line[mid] , x)){
					pos = mid;
					high = mid - 1;
				}
				else low = mid + 1;
			}
			order.push_back({cur_size , pos , line[pos]});
			cur_size = pos + 1;
			line[pos] = x;
			return;
		}
		
		LL Get(LL x){
			int low = 1 , high = cur_size - 1 , pos = 0;
			while (low<=high){
				int mid = (low+high)/2;
				if (get_intersec(line[mid-1],line[mid]) <= x){
					pos = mid;
					low = mid + 1;
				}
				else high = mid-1;
			}
			return line[pos].F(x);
		}
		
		void rollback(void){
			if (order.size()==0) return;
			int size = order.back().size;
			int pos = order.back().add_pos;
			Line val = order.back().val;
			
			cur_size = size; line[pos] = val;

			order.pop_back();
			return ;
		}
};
CHT baoloi;

int n;

LL d[N+2] , dp[N+2];
int st[N+2] , speed[N+2];

vector<pair<int,int>>ke[N+2];
	void add_canh(int u,int v,int w){
		ke[u].push_back({v,w}) , 
		ke[v].push_back({u,w});
		return;
	}

	void dfs(int u,int p = 0){
		if (p==0) dp[u] = 0; else {
			dp[u] = st[u] + d[u] * speed[u] - baoloi.Get(speed[u]);
		}
		baoloi.add_line(Line(d[u] , -dp[u]));
		
		
		for(auto&v:ke[u]){
			if (v.first==p) continue;
			d[v.first] = d[u] + v.second;
			dfs(v.first , u);
		}
		
		baoloi.rollback();
		return;
		
	}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0) ;
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		
		cin>>n;
		for(int i = 1; i < n; ++i) {
			int u,v,w; cin>>u>>v>>w;
			add_canh(u,v,w);
		}
		baoloi.reload_size(n);
		for(int i = 2; i <= n; ++i) cin>>st[i]>>speed[i];
		dfs(1);
		for(int i = 2; i <= n; ++i) cout<<dp[i]<<' '; cout<<'\n';
		return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:116:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:117:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |                         freopen(name".out","w",stdout);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100