Submission #965242

#	Time	Username	Problem	Language	Result	Execution time	Memory
965242		hhnguyen	Harbingers (CEOI09_harbingers)	C++14	30 / 100	86 ms	22612 KiB

harbingers

#include<bits/stdc++.h>
#define ll long long
#define pb push_back

using namespace std;
const int N = 1e5+5;
typedef pair <ll,ll> ii;
vector <ii> graph[N];
struct Line{
	int m,c;

	int value(int x){
		return m*x + c;
	}

	double intersect(Line D){
		return ((c - D.c)/(D.m - m));
	}
};
ll n;
ll V[N],S[N],dp[N],curr_sz = 0;
Line L[N];

int min_val(int x){
	int lo = 0; int hi = curr_sz-1;

	while(lo < hi){
		int mid = (lo+hi)/2;

		if(L[mid].intersect(L[mid+1]) < x){
			lo = mid+1;
		}

		else{
			hi = mid;
		}
	}

	return L[lo].value(x);
}

int pos(Line D){
	if(curr_sz <= 1 || D.intersect(L[curr_sz-1]) > L[curr_sz-1].intersect(L[curr_sz-2])){
		return curr_sz;
	}

	int lo = 1; int hi = curr_sz-1;

	while(lo < hi){
		int mid = (lo+hi)/2;

		if(D.intersect(L[mid]) < L[mid].intersect(L[mid-1])){
			hi = mid;
		}

		else{
			lo = mid+1;
		}
	}

	return lo;
}
void dfs(int src, int prev, int d){
	for(auto [ch,dist] : graph[src]){
		if(ch == prev) continue;
		dp[ch] = min_val(V[ch]) + V[ch]*(d+dist) + S[ch];

		Line D = {-d-dist,dp[ch]};
		int curr = curr_sz;
		int curr_pos = curr_sz = pos(D); Line pre = L[curr_pos];
		L[curr_pos] = D; curr_sz++;


		dfs(ch,src,d+dist);

		//reset the changes

		L[curr_pos] = pre; curr_sz = curr;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n;
	for(ll i=1;i<n;i++)
    {
		ll a,b,c;
		cin >> a >> b >> c;
		graph[a].pb({b,c}); graph[b].pb({a,c});
	}

	for(ll i=2;i<=n;i++){
		cin >> S[i] >> V[i];
	}

	L[0] = {0,0}; curr_sz++;
	dfs(1,-1,0);

	for(ll i=2;i<=n;i++){
		cout << dp[i] << " ";
	}
	return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'void dfs(int, int, int)':
harbingers.cpp:64:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |  for(auto [ch,dist] : graph[src]){
      |           ^
harbingers.cpp:68:15: warning: narrowing conversion of '(((std::tuple_element<1, std::pair<long long int, long long int> >::type)(- d)) - dist)' from 'std::tuple_element<1, std::pair<long long int, long long int> >::type' {aka 'long long int'} to 'int' [-Wnarrowing]
   68 |   Line D = {-d-dist,dp[ch]};
      |             ~~^~~~~
harbingers.cpp:68:26: warning: narrowing conversion of 'dp[ch]' from 'long long int' to 'int' [-Wnarrowing]
   68 |   Line D = {-d-dist,dp[ch]};
      |                     ~~~~~^

• Subtask 1: 30 / 100