Submission #978646

#	Time	Username	Problem	Language	Result	Execution time	Memory
978646		raspy	Harbingers (CEOI09_harbingers)	C++14	40 / 100	1088 ms	33620 KiB

harbingers

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

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

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

struct ln
{
	int m, c;
	double p;
};

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

double getX(int m1, int c1, int m2, int c2) { return (double)(c1- c2)/(m2- m1); }

vector<ln> dodaj(int m, int c)
{
	vector<ln> iz;
	double p = -inf;
	while (!ch.empty())
	{
		p = getX(m, c, ch.back().m, ch.back().c);
		if (p < ch.back().p-EPS)
		{
			iz.push_back(ch.back());
			ch.pop_back();
		}
		else
			break;
	}
	ch.push_back({m, c, p});
	return iz;
}

int getBestY(int x) {
	int k = 0;
	int L = 0, R = ch.size()- 1;
	while (L <= R)
	{
		int mid = (L+R) >> 1;
		if (ch[mid].p <= x+EPS)
			k = mid, L = mid+1;
		else
			R = mid-1;
	}
	return ch[k].m*x + ch[k].c;
}

void dfs(int u = 1, int gl = 0, int p = -1)
{
	int zv = gl*hr[u].second+hr[u].first;
	if (!ch.empty())
		zv += getBestY(hr[u].second);
	dp[u] = zv;
	vector<ln> iz = dodaj(-gl, zv);
	for (auto [v, d] : graf[u])
		if (v != p)
			dfs(v, gl+d, u);
	ch.pop_back();
	for (auto l : iz)
		ch.push_back(l);
}

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 'void dfs(long long int, long long int, long long int)':
harbingers.cpp:65:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |  for (auto [v, d] : graf[u])
      |            ^

• Subtask 1: 40 / 100