Submission #1209768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209768		thewizardman	Harbingers (CEOI09_harbingers)	C++20	0 / 100	107 ms	131072 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pil pair<int, ll>

int n, dist[100001];
vector<pii> adj[100001];
ll dp[100001];
pii h[100001];
deque<pil> dq;

ll eval(pil line, ll x) { return (ll)line.first*x + line.second; }
ld its_x(pil l1, pil l2) { return (ld) (l2.second - l1.second) / (l1.first - l2.first); }

// dp[i] = dp[j] + (dist[i] - dist[j]) * h[i].second + h[i].first
// dp[i] = -dist[j]*h[i].second + dp[j] + (h[i].second*dist[i] + h[i].first)

void dfs(int u, int p) {
  stack<pil> front, back;
  while (dq.size() >= 2 && eval(dq.back(), h[u].second) >= eval(dq[dq.size()-2], h[u].second)) {
    back.push(dq.back());
    dq.pop_back();
  }
  dp[u] = eval(dq.back(), h[u].second) + (ll)h[u].second*dist[u] + (ll)h[u].first;
  pil cur = {-dist[u], dp[u]};
  while (dq.size() >= 2 && its_x(dq[0], cur) <= its_x(dq[0], dq[1])) {
    front.push(dq.front());
    dq.pop_front();
  }
  dq.push_front(cur);
  for (auto [v, w]: adj[u]) if (v != p) dist[v] = dist[u] + w, dfs(v, u);
  dq.pop_front();
  while (!front.empty()) dq.push_front(front.top()), front.pop();
  while (!back.empty()) dq.push_back(back.top()), back.pop();
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n;
  for (int i = 1; i < n; i++) {
    int u, v; ll 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 >> h[i].first >> h[i].second;
  dq.push_back({0, 0});
  dfs(1, -1);
  for (int i = 2; i <= n; i++) cout << dp[i] << ' ';
}

• Subtask 1: 0 / 100