Submission #885776

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
885776	2023-12-10T16:51:04 Z	peterandvoi	Harbingers (CEOI09_harbingers)	C++17	100 / 100	79 ms	26844 KB

harbingers

#include <bits/stdc++.h>

using namespace std;

#define db(...) " [" << #__VA_ARGS__ << " : " << (__VA_ARGS__) << "] "

const int N = 100005;

int n;
int s[N], c[N];
long long dp[N], d[N];
vector<pair<int, int>> g[N];

long double Div(long long a, long long b) {
  return 1.0L * a / b;
}  

struct Line {
  long long k, m;
  
  Line() {};
  
  Line(long long k, long long m): k(k), m(m) {};
  
  long long eval(long long x) const {
    return k * x + m;
  }  
};

bool bad(const Line &a, const Line &b, const Line &c) {
  return Div(b.m - a.m, a.k - b.k) >= Div(c.m - a.m, a.k - c.k);
}

struct convex_hull_rollback {
  int n = 0;
  Line a[N];
  stack<tuple<int, Line>> st;
  
  void add(long long k, long long m) {
    Line x = {k, m};
    int l = 2, r = n, pos = n + 1;
    while (l <= r) {
      int mid = l + r >> 1;
      if (bad(a[mid - 1], a[mid], x)) {
        r = mid - 1;
        pos = mid;
      } else {
        l = mid + 1;
      }
    }
    st.emplace(n, a[pos]);
    n = pos;
    a[n] = x;
  }
  
  long long query(long long x) {
    int l = 2, r = n, pos = 1;
    while (l <= r) {
      int mid = l + r >> 1;
      if (a[mid - 1].eval(x) > a[mid].eval(x)) {
        pos = mid;
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
    return a[pos].eval(x);
  }
  
  void rollback() {
    auto [prv, l] = st.top();
    st.pop();
    a[n] = l;
    n = prv;
  }
};

convex_hull_rollback cht;

void dfs(int u = 1, int par = 1) {
  if (u != 1) {
    dp[u] = cht.query(c[u]) + 1LL * d[u] * c[u] + s[u]; 
  }
  cht.add(-d[u], dp[u]);
  for (auto [v, w] : g[u]) {
    if (v != par) {
      d[v] = d[u] + w;
      dfs(v, u);    
    }
  }
  cht.rollback();
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for (int i = 1, u, v, w; i < n; ++i) {
    cin >> u >> v >> w;
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
  }
  for (int i = 2; i <= n; ++i) {
    cin >> s[i] >> c[i];
  }
  dfs();
  for (int i = 2; i <= n; ++i) {
    cout << dp[i] << " ";
  }
}

Compilation message

harbingers.cpp: In member function 'void convex_hull_rollback::add(long long int, long long int)':
harbingers.cpp:43:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |       int mid = l + r >> 1;
      |                 ~~^~~
harbingers.cpp: In member function 'long long int convex_hull_rollback::query(long long int)':
harbingers.cpp:59:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |       int mid = l + r >> 1;
      |                 ~~^~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	2 ms	4956 KB	Output is correct
3	Correct	29 ms	13676 KB	Output is correct
4	Correct	43 ms	18260 KB	Output is correct
5	Correct	55 ms	22360 KB	Output is correct
6	Correct	79 ms	26844 KB	Output is correct
7	Correct	36 ms	13056 KB	Output is correct
8	Correct	69 ms	17872 KB	Output is correct
9	Correct	76 ms	21076 KB	Output is correct
10	Correct	66 ms	19408 KB	Output is correct