Submission #792893

#	Time	Username	Problem	Language	Result	Execution time	Memory
792893		winthemcut3	Harbingers (CEOI09_harbingers)	C++14	100 / 100	102 ms	25812 KiB

harbingers

#include <bits/stdc++.h>
#define FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define PB push_back
#define ALL(v) (v).begin(), (v).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; i--)
#define fi   first
#define se   second
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;

/** END OF TEMPLATE **/

const int mxN = 1e5 + 5;
typedef pair<int, int> pii;
int n;
vector<pii> g[mxN];
ll f[mxN], s[mxN], t[mxN];
struct line {
    ll a, b;
    line() = default;
    line(ll a_, ll b_) : a(a_), b(b_) {}
    ll f(ll x) { return a*x + b; }
};
struct opt {
    int id, sz;
    line L;
    opt() = default;
    opt(int id_, int sz_, line L_) : id(id_), sz(sz_), L(L_) {}
};
stack<opt> st;
line Y[mxN];
struct CHTrick {
    int sz;
    CHTrick() { sz = 0; }
    bool invalid(const line &l1, const line &l2, const line &l3) {
        return (long double)(l3.b - l1.b)/(l1.a - l3.a) >= (long double)(l2.b - l1.b)/(l1.a - l2.a);
    }
    void add(line L) {
        int l = 0, r = sz - 1, k = sz;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(mid > 0 && invalid(Y[mid-1], Y[mid], L)) {
                k = mid; r = mid-1;
            } else l = mid+1;
        }
        st.push({k, sz, Y[k]});
        Y[k] = L; sz = k+1;
    }
    ll getMin(ll x) {
        int l = 0, r = sz-1;
        while(l < r) {
            int mid = (l + r) >> 1;
            if(Y[mid].f(x) > Y[mid+1].f(x)) l = mid+1;
            else r = mid;
        }
        return Y[l].f(x);
    }
};
ll d[mxN];
CHTrick CH;
void dfs(int u, int par) {
    CH.add(line(d[u], f[u]));
    for(auto &it : g[u]) {
        int v = it.fi; ll c = it.se;
        if(v == par) continue;
        d[v] = d[u] + c;
        f[v] = CH.getMin(-t[v]) + s[v] + 1ll*t[v]*d[v];
        dfs(v, u);
    }
    opt tmp = st.top(); st.pop();
    Y[tmp.id] = tmp.L;
    CH.sz = tmp.sz;
}
int main()
{
    FastIO;
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    cin >> n;
    FOR(i, 1, n-1) {
        int u, v, c; cin >> u >> v >> c;
        g[u].PB({v, c}); g[v].PB({u, c});
    }
    FOR(i, 2, n)
        cin >> s[i] >> t[i];
    dfs(1, 0);
    FOR(i, 2, n) cout << f[i] << ' ';
    return 0;
}

/*

*/

• Subtask 1: 100 / 100