Submission #1335665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1335665		ahmedalaa22	Harbingers (CEOI09_harbingers)	C++20	100 / 100	64 ms	24000 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define all(s) s.begin(), s.end()
#define rall(s) s.rbegin(), s.rend()
#define sz(s) (int)s.size()
#define F first
#define S second
#define endl '\n'

const int N = 1e5 + 11;
const int MXBIT = 20, MAXN = 3e6 + 7;
const int M = 100005;

const ll INF = 1e17;

template<bool IS_MAX = false, bool IS_INC = false>
struct RollbackCHT {
    struct Line {
        ll m, c;
        Line() : m(0), c(INF) {}
        Line(ll m, ll c) : m(m), c(c) {}
        ll eval(ll x) const { return m * x + c; }
    };

    struct History {
        int pos;
        int sz;
        Line old_line;
    };

    vector<Line> st;
    vector<History> hist;
    int sz;

    RollbackCHT(int max_nodes) {
        st.resize(max_nodes);
        sz = 0;
    }

    bool redundant(Line l1, Line l2, Line l3) {
        __int128 dx1 = l1.m - l2.m;
        __int128 dc1 = l2.c - l1.c;
        __int128 dx2 = l2.m - l3.m;
        __int128 dc2 = l3.c - l2.c;
        return dc1 * dx2 >= dc2 * dx1;
    }

    void add(ll m, ll c) {
        ll m_int = IS_INC ? -m : m;
        ll c_int = IS_MAX ? -c : c;

        Line l_new(m_int, c_int);
        int pos = sz;
        int low = 1, high = sz - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (redundant(st[mid - 1], st[mid], l_new)) {
                pos = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        hist.push_back({pos, sz, st[pos]});
        st[pos] = l_new;
        sz = pos + 1;
    }

    void rollback() {
        if (hist.empty()) return;
        History h = hist.back();
        hist.pop_back();
        sz = h.sz;
        st[h.pos] = h.old_line;
    }

    ll query(ll x) {
        if (sz == 0) return IS_MAX ? -INF : INF;

        ll x_int = (IS_INC != IS_MAX) ? -x : x;
        
        int low = 0, high = sz - 2;
        int best = sz - 1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (st[mid].eval(x_int) <= st[mid + 1].eval(x_int)) {
                best = mid;
                high = mid - 1; 
            } else {
                low = mid + 1;  
            }
        }
        
        ll ans = st[best].eval(x_int);
        return IS_MAX ? -ans : ans;
    }
};

void solve() {
    int n;
    cin >> n;
    vector<pair<int, int> > adj[n + 1];
    for (int i{1}; i < n; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    vector<int> a(n + 1), b(n + 1);
    vector<ll> d(n + 1);
    for (int i{2}; i <= n; ++i) cin >> a[i] >> b[i];
    
    RollbackCHT<false, false> cht(N);
    cht.add(0, 0);
    
    vector<ll> dp(n + 1);
    dp[0] = 0;
    
    function<void(int, int, ll)> dfs = [&](int u, int p, ll s) {
        dp[u] = cht.query(b[u]) + s * b[u] + a[u];
        cht.add(-s, dp[u]);
        
        for (auto &[v, w]: adj[u]) {
            if (v == p) continue;
            dfs(v, u, s + w);
        }
        
        cht.rollback();
    };
    
    dfs(1, 0, 0);
    for (int i{2}; i <= n; ++i) cout << dp[i] << " ";
    cout << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    clock_t start = clock();
    while (t--) solve();
    clock_t end = clock();
    double time_spent = (double) (end - start) / CLOCKS_PER_SEC;
    return 0;
}

• Subtask 1: 100 / 100