Submission #993578

#	Time	Username	Problem	Language	Result	Execution time	Memory
993578		efishel	Harbingers (CEOI09_harbingers)	C++17	20 / 100	122 ms	65536 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector <ll>;
using ii = pair <ll, ll>;

const ll MAXN = 1E5+16, INF = ll(1E18)+16;
vector <pair <int, int> > adj[MAXN];
ll dp[MAXN];
int dis[MAXN];
int sleep[MAXN], slow[MAXN];

#define mid ((l+r)>>1)
#define eval(p, x) (p.first*ll(x) + p.second)
struct SegTree {
    SegTree *left, *right;
    int l, r;
    ii f;

    SegTree (int l, int r): left(0), right(0), l(l), r(r), f({0, INF}) {}

    void update (ii g, vector <vector <pair <SegTree*, ii> > > &ups) {
        bool isL = eval(g, l) < eval(f, l);
        bool isM = eval(g, mid) < eval(f, mid);
        if (isM) {
            ups.back().push_back({ this, f });
            swap(f, g);
        }
        if (l == r || g == ii{0, INF}) return;
        if (isL != isM) {
            if (!left) left = new SegTree(l, mid);
            left->update(g, ups);
        } else {
            if (!right) right = new SegTree(mid+1, r);
            right->update(g, ups);
        }
    }

    ll query (ll x) {
        if (x <= mid)
            return min(eval(f, x), left ? left->query(x) : INF);
        else
            return min(eval(f, x), right ? right->query(x) : INF);
    }
} st(0, 1E9);

vector <vector <pair <SegTree*, ii> > > ups;

void rollback () {
    auto th = ups.back(); ups.pop_back();
    for (auto [stPtr, lastFun] : th) {
        stPtr->f = lastFun;
    }
}

void dfs (ll u, ll par) {
    dp[u] = ll(sleep[u])+ll(slow[u])*dis[u];
    dp[u] = min(dp[u], st.query(slow[u])  +ll(sleep[u])+ll(slow[u])*dis[u]);
    ups.push_back({});
    st.update({-dis[u], dp[u]}, ups);
    for (auto [v, w] : adj[u]) {
        if (v == par) continue;
        dis[v] = dis[u]+w;
        dfs(v, u);
    }
    rollback();
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n;
    cin >> n;
    for (ll i = 1; i < n; i++) {
        ll u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
    }
    for (ll i = 1; i < n; i++) cin >> sleep[i] >> slow[i];
    dis[0] = 0;
    dp[0] = 0;
    dfs(0, 0);
    for (ll i = 1; i < n; i++) cout << dp[i] << ' ';
    cout << '\n';
    return 0;
}

• Subtask 1: 20 / 100