Submission #978666

#	Time	Username	Problem	Language	Result	Execution time	Memory
978666		raspy	Harbingers (CEOI09_harbingers)	C++14	100 / 100	189 ms	24660 KiB

harbingers

#include <iostream>
#include <vector>
#include <algorithm>

#define EPS 0.0000001
#define inf 1'000'000'000'000'000'000
#define int long long
#define double long double

using namespace std;
typedef pair<int, int> ii;

struct ln
{
	int m, c;
};

vector<ii> graf[200005];
ii hr[200005]; // c, m
ln ch[200005];
int sz = 0;
int dp[200005];

double getX(ln l1, ln l2) { return (double)(l2.c-l1.c)/(l1.m-l2.m); }

int getBestY(int x)
{
	int k = 0;
	int L = 0, R = sz-1;
	while (L < R)
	{
		int mid = (L+R)/2;
		if (getX(ch[mid], ch[mid+1]) < x)
			L = mid+1;
		else
			R = mid;
	}
	return ch[L].m*x + ch[L].c;
}

int izbris(ln line)
{
	if (sz < 2 || getX(line, ch[sz-1]) >= getX(ch[sz-1], ch[sz-2]))
		return sz;
	int l = 1, r = sz - 1;
	while (l < r)
	{
		int mid = (l + r) / 2;
		if (getX(line, ch[mid]) < getX(ch[mid], ch[mid-1]))
			r = mid;
		else
			l = mid+1;
	}
	return l;
}

void dfs(int u = 1, int gl = 0, int p = -1)
{
	int zv = gl*hr[u].second+hr[u].first;
	ln pr;
	int osz = 0, prix = 0;
	if (sz)
	{
		zv += getBestY(hr[u].second);
		osz = sz;
		ln l = {-gl, zv};
		prix = sz = izbris(l);
		pr = ch[sz];
		ch[sz++] = l;
	}
	else
		ch[sz++] = {-gl, zv};
	dp[u] = zv;
	for (auto [v, d] : graf[u])
		if (v != p)
			dfs(v, gl+d, u);
	if (u != 1)
	{
		sz = osz;
		ch[prix] = pr;
	}
}

int32_t main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n-1; i++)
	{
		int u, v, d;
		cin >> u >> v >> d;
		graf[u].push_back({v, d});
		graf[v].push_back({u, d});
	}
	for (int i = 1; i < n; i++)
		cin >> hr[i+1].first >> hr[i+1].second;
	dfs();
	for (int i = 2; i <= n; i++)
		cout << dp[i] << " ";
	cout << "\n";
	return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'long long int getBestY(long long int)':
harbingers.cpp:28:6: warning: unused variable 'k' [-Wunused-variable]
   28 |  int k = 0;
      |      ^
harbingers.cpp: In function 'void dfs(long long int, long long int, long long int)':
harbingers.cpp:74:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |  for (auto [v, d] : graf[u])
      |            ^

• Subtask 1: 100 / 100