Submission #1235269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235269		sh1ft	Harbingers (CEOI09_harbingers)	C++17	70 / 100	1095 ms	31044 KiB

harbingers

/*
    author  : sh1ft
    created : 08/07/2025 07:50
    task    : CEOI09_harbingers
*/
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int mxN = 1e5+5;

int n;
ll q[mxN], a[mxN], b[mxN], dp[mxN];
vector <pair <int, ll>> adj[mxN];
vector <int> iter;
deque <int> cht;

void build(int u, int p) { for (auto &[v, w] : adj[u]) if (v != p) q[v] = q[u] + w, build(v, u); }
ll calc(ll x, int j) { return -q[j]*x + dp[j]; }
long double m(int x, int y) { return (long double) (calc(0, x) - calc(0, y))/((-q[y])-(-q[x])); }
bool cmp(int idx, ll x) { return m(cht[idx], cht[idx+1]) <= x; }

void dfs(int u, int p) {
    for (auto [v, w] : adj[u]) if (v != p) {
        vector <int> del;
        int idx = cht[*lower_bound(iter.begin(), iter.begin()+cht.size()-1, a[v], cmp)];
        dp[v] = calc(a[v], idx) + q[v]*a[v] + b[v];
        while (cht.size() > 1 && m(cht[cht.size()-1], v) <= m(cht[cht.size()-1], cht[cht.size()-2])) del.emplace_back(cht[cht.size()-1]), cht.pop_back();
        cht.emplace_back(v);
        dfs(v, u);
        cht.pop_back();
        while (!del.empty()) cht.emplace_back(del.back()), del.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n; iter.resize(n+10); iota(iter.begin(), iter.end(), 0);
    for (int i = 1; i < n; i++) { int u, v; ll w; cin >> u >> v >> w; adj[u].emplace_back(v, w); adj[v].emplace_back(u, w); }
    build(1, 1);
    for (int i = 2; i <= n; i++) cin >> b[i] >> a[i];
    cht.emplace_back(1);
    dfs(1, 1);
    for (int i = 2; i <= n; i++) cout << dp[i] << ' '; cout << '\n';
}

/*
dp[i] = min(dp[j] + (p[i] - p[j])*a[i] + b[i])
      = min(dp[j] + p[i]*a[i] - p[j]*a[i] + b[i])
      = p[i]*a[i] + b[i] + min(-p[j]*a[i] + dp[j])
*/

• Subtask 1: 70 / 100