Submission #935865

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
935865	2024-02-29T18:07:28 Z	Blagoj	Harbingers (CEOI09_harbingers)	C++17	60 / 100	144 ms	37948 KB

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;

int n, SIZE;

set<ll> comp;
vector<ll> dists;
vector<pair<ll, ll>> g[mxn];

struct Line {
    ll m = 0, b = -1e14;
};

ll vals[mxn];

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

stack<pair<ll, Line>> s;

struct LiChao {
    int cnt = 1;
    vector<Line> sgt;
 
    LiChao() {
        sgt.resize(1 << 18);
    }
 
    void update(int k, int l, int r, Line 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);
    }
 
    ll get(int k, int l, int r, ll x) {
        if (l > x || r < x) return -1e14;
        int mid = (l + r) / 2;
        ll 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) {
            swap(sgt[s.top().first], s.top().second);
            s.pop();
        }
    }
} lc;

ll dist[mxn], ans[mxn], 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 = 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] + speed[cur] * 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++) comp.insert(speed[i]);
    int cnt = 0;
    for (auto x : comp) {
        vals[cnt++] = x;
        dists.push_back(x);
    }
    SIZE = comp.size();
    comp.clear();
    lc.update(1, 0, SIZE - 1, {0, 0});
    dfs();
    for (int i = 2; i <= n; i++) cout << ans[i] << " ";
}

Compilation message

harbingers.cpp: In member function 'void LiChao::rollback(int)':
harbingers.cpp:67: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]
   67 |         while (s.size() > x) {
      |                ~~~~~~~~~^~~

Subtask #1

60.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	10584 KB	Output is correct
2	Correct	5 ms	11356 KB	Output is correct
3	Correct	54 ms	24200 KB	Output is correct
4	Runtime error	73 ms	33700 KB	Memory limit exceeded
5	Correct	115 ms	32500 KB	Output is correct
6	Runtime error	115 ms	33112 KB	Memory limit exceeded
7	Correct	63 ms	19976 KB	Output is correct
8	Correct	126 ms	31388 KB	Output is correct
9	Runtime error	144 ms	37948 KB	Memory limit exceeded
10	Runtime error	111 ms	34188 KB	Memory limit exceeded