Submission #935862

#	Time	Username	Problem	Language	Result	Execution time	Memory
935862		Blagoj	Harbingers (CEOI09_harbingers)	C++17	60 / 100	109 ms	64088 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()

const int mxn = 1e5 + 10;

vector<pair<ll, ll>> g[mxn];

struct Line {
    ll m = 0, b = -1e14;
    int l, r, lp = -1, rp = -1;
};

void swap(Line &a, Line &b) {
    swap(a.m, b.m);
    swap(a.b, b.b);
}

ll f(Line a, ll x) {
    return a.m * x + a.b;
}

stack<pair<ll, Line>> s;

struct LiChao {
    int cnt = 1;
    vector<Line> sgt;
 
    LiChao() {
        sgt.resize(1e4);
        sgt[1].l = 1;
        sgt[1].r = 1e9;
    }
 
    void update(int k, Line nw) {
        int l = sgt[k].l, r = sgt[k].r, mid = (l + r) / 2;
        if (f(nw, l) <= f(sgt[k], l) && f(nw, r) <= f(sgt[k], r)) return;
        if (f(nw, l) >= f(sgt[k], l) && f(nw, r) >= f(sgt[k], r)) {
            s.push({k, sgt[k]});
            swap(sgt[k], nw);
            return;
        }
        bool f1 = f(nw, l) > f(sgt[k], l);
        bool f2 = f(nw, mid) > f(sgt[k], mid);
        if (f2) {
            s.push({k, sgt[k]});
            swap(sgt[k], nw);
        }
        if (l == r) return;
        if (f1 != f2) {
            if (sgt[k].lp == -1) {
                sgt[k].lp = ++cnt;
                sgt[cnt].l = l;
                sgt[cnt].r = mid;
            }
            update(sgt[k].lp, nw);
        }
        else {
            if (sgt[k].rp == -1) {
                sgt[k].rp = ++cnt;
                sgt[cnt].l = mid + 1;
                sgt[cnt].r = r;
            }
            update(sgt[k].rp, nw);
        }
    }
 
    ll get(int k, ll x) {
        int l = sgt[k].l, r = sgt[k].r, mid = (l + r) / 2;
        ll ans = f(sgt[k], x);  
        if (x <= mid) {
            if (sgt[k].lp != -1) ans = max(ans, get(sgt[k].lp, x)); 
        }
        else if (sgt[k].rp != -1) ans = max(ans, get(sgt[k].rp, x));
        return ans;
    }

    void rollback(int x) {
        while (s.size() > x) {
            swap(sgt[s.top().first], s.top().second);
            s.pop();
        }
    }
} lc;

ll dist[mxn], ans[mxn], start[mxn], speed[mxn];

void dfs(int cur = 1, int par = -1) {
    int sz = s.size();
    if (cur != 1) {
        ans[cur] = -lc.get(1, speed[cur]) + start[cur] + speed[cur] * dist[cur];
        lc.update(1, {dist[cur], -ans[cur]});
    }
    for (auto x : g[cur]) {
        if (x.first != par) {
            dist[x.first] = dist[cur] + x.second;
            dfs(x.first, cur);
        }
    }
    lc.rollback(sz);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lc.update(1, {0, 0});
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int f, t, w;
        cin >> f >> t >> w;
        g[f].push_back({t, w});
        g[t].push_back({f, w});
    }
    for (int i = 2; i <= n; i++) cin >> start[i] >> speed[i];
    dfs();
    for (int i = 2; i <= n; i++) cout << ans[i] << " ";
}

Compilation message (stderr)

harbingers.cpp: In member function 'void LiChao::rollback(int)':
harbingers.cpp:83:25: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<long long int, Line> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |         while (s.size() > x) {
      |                ~~~~~~~~~^~~

• Subtask 1: 60 / 100