제출 #993566

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
993566		efishel	Harbingers (CEOI09_harbingers)	C++17	20 / 100	130 ms	65536 KiB

harbingers

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

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

#define mid ((l+r)>>1)
struct SegTree {
    struct Fun {
        ll a, b;

        ll operator() (ll x) const { return a*x + b; }
    };
    SegTree *left, *right;
    ll l, r;
    Fun f;

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

    void update (Fun g, vector <vector <pair <SegTree*, SegTree::Fun> > > &ups) {
        bool isL = g(l) < f(l);
        bool isM = g(mid) < f(mid);
        if (isM) {
            ups.back().push_back({ this, f });
            swap(f, g);
        }
        if (l == r || g.a == 0 && g.b == 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(f(x), left ? left->query(x) : INF);
        else
            return min(f(x), right ? right->query(x) : INF);
    }
} st(0, 1E9);

vector <vector <pair <SegTree*, SegTree::Fun> > > ups;

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

vll stk;
void dfs (ll u, ll par) {
    dp[u] = sleep[u]+slow[u]*dis[u];
    dp[u] = min(dp[u], st.query(slow[u])  +sleep[u]+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;
}

컴파일 시 표준 에러 (stderr) 메시지

harbingers.cpp: In member function 'void SegTree::update(SegTree::Fun, std::vector<std::vector<std::pair<SegTree*, SegTree::Fun> > >&)':
harbingers.cpp:33:32: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   33 |         if (l == r || g.a == 0 && g.b == INF) return;
      |                       ~~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 20 / 100