Submission #935924

#	Time	Username	Problem	Language	Result	Execution time	Memory
935924		Blagoj	Harbingers (CEOI09_harbingers)	C++17	90 / 100	124 ms	33260 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 + 1;

int n, SIZE;

vector<int> dists;
vector<pair<int, int>> g[mxn];

long f(pair<int, long> a, int x) {
    return (long) a.first * (long) dists[x] + a.second;
}


struct LiChao {
    stack<pair<int, pair<int, long>>> s;
    vector<pair<int, long>> sgt;
 
    LiChao() {
        sgt.resize(1 << 18);
    }
 
    void update(int k, int l, int r, pair<int, long> nw) {
        int 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) update(k * 2, l, mid, nw);
        else update(k * 2 + 1, mid + 1, r, nw);
    }
 
    long get(int k, int l, int r, int x) {
        if (l > x || r < x) return -1e14;
        int mid = (l + r) / 2;
        long ans = f(sgt[k], x);  
        if (l == r) return ans;
        ans = max(ans, get(k * 2, l, mid, x)); 
        ans = max(ans, get(k * 2 + 1, mid + 1, r, x));
        return ans;
    }

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

long ans[mxn];
int dist[mxn];
int start[mxn], speed[mxn];

void getDists(int cur = 1, int par = -1) {
    for (auto x : g[cur]) {
        if (x.first != par) {
            dist[x.first] = dist[cur] + x.second;
            getDists(x.first, cur);
        }
    }
}

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    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];
    getDists();
    for (int i = 1; i <= n; i++) dists.push_back(speed[i]);
    sort(all(dists));
    dists.erase(unique(all(dists)), dists.end());
    SIZE = dists.size();
    lc.update(1, 0, SIZE - 1, {0, 0});
    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:59:25: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, std::pair<int, long int> > >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |         while (s.size() > x) {
      |                ~~~~~~~~~^~~

• Subtask 1: 90 / 100