Submission #888084

#	Time	Username	Problem	Language	Result	Execution time	Memory
888084		ikaurov	Harbingers (CEOI09_harbingers)	C++17	100 / 100	74 ms	22824 KiB

harbingers

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define all(arr) (arr).begin(), (arr).end()
#define ll long long
#define ld long double
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define endl '\n'

const int N = 1e5 + 20;
const ll INF = 2e18;

struct line{
  ll k, b;

  ll f(int x){
    return k * 1ll * x + b;
  }
};

void add_line(vector<line>& hull, line l){
  while (sz(hull) > 1){
    line& l1 = hull.end()[-2], l2 = hull.end()[-1];
    if ((__int128_t)(l.b - l1.b) * (l2.k - l.k) >= (__int128_t)(l.b - l2.b) * (l1.k - l.k)){
      hull.pop_back();
    }
    else break;
  }
  hull.pb(l);
}

ll get(vector<line>& hull, int x){
  if (hull.empty()) return INF;
  int l = 0, r = sz(hull);
  while (r - l > 1){
    int mid = (l + r) / 2;
    if (hull[mid].f(x) < hull[mid - 1].f(x)) l = mid;
    else r = mid;
  }
  return hull[l].f(x);
}

vector<vector<line>> hulls;
vector<pair<int, int>> g[N];
int sz[N], s[N], vel[N];
ll dp[N], dist[N];

void dfs_prep(int v, int p = 0){
  if (p){
    int idx;
    for (int i = 0; i < sz(g[v]); i++){
      if (g[v][i].fi == p) idx = i;
    }
    g[v].erase(g[v].begin() + idx);
  }
  sz[v] = 1;
  int node = 0, idx;
  for (int i = 0; i < sz(g[v]); i++){
    int u = g[v][i].fi, w = g[v][i].se;
    dist[u] = dist[v] + w;
    dfs_prep(u, v);
    sz[v] += sz[u];
    if (!node || sz[node] < sz[u]) node = u, idx = i;
  }
  if (node) swap(g[v].back(), g[v][idx]);
}

void dfs(int v){
  if (v != 1){
    dp[v] = INF;
    for (auto& hull : hulls) dp[v] = min(dp[v], s[v] + dist[v] * vel[v] + get(hull, vel[v]));
  }
  line cur;
  cur.k = -dist[v], cur.b = dp[v];
  add_line(hulls.back(), cur);

  for (auto [u, w] : g[v]){
    if (u == g[v].back().fi){
      dfs(u);
      continue;
    }
    hulls.emplace_back();
    dfs(u);
    hulls.pop_back();
  }
}

signed main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  // cout.precision(20);
  int n;
  cin >> n;
  for (int i = 1; i < n; i++){
    int u, v, d;
    cin >> u >> v >> d;
    g[u].pb({v, d});
    g[v].pb({u, d});
  }
  for (int i = 2; i <= n; i++) cin >> s[i] >> vel[i];
  dfs_prep(1);
  hulls.emplace_back();
  dfs(1);
  for (int i = 2; i <= n; i++) cout << dp[i] << " ";
  cout << endl;
}

Compilation message (stderr)

harbingers.cpp: In function 'void dfs_prep(int, int)':
harbingers.cpp:53:9: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   53 |     int idx;
      |         ^~~

• Subtask 1: 100 / 100