Submission #1263181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263181		amigoo99234	Harbingers (CEOI09_harbingers)	C++20	60 / 100	1096 ms	35544 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;

//long long MOD = 1e9 + 7;
const long long MOD = 998244353;
// const long long MOD = 100000007 ;


#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

#define popCnt(x) (__builtin_popcountll(x))
#define int long long
#define ld long double

#define F  first
#define S  second
#define pi  M_PI
#define all(x) x.begin() , x.end()
#define LL long long
#define SZ(v) (int)(v.size())

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
const long long OO = LLONG_MAX / 4, N = 3e5 + 5, M = 1e5 + 5, K = 505;


using ll = long long;
const long double NINF = -1e300L;
const long double PINF =  1e300L;

struct Line {
    ll a, b; // y = a*x + b
    Line(ll a = 0, ll b = LLONG_MIN) : a(a), b(b) {}
    inline ll eval(ll x) const { return a * x + b; }
};

struct Op {
    bool added;                       // whether we actually added a line
    vector<Line> removed_lines;       // lines removed from the back while adding
    vector<long double> removed_xs;   // their associated intersection x-values
};

struct RollbackableCHT {
    // lines[i] is active line for interval x >= xs[i]
    vector<Line> lines;
    vector<long double> xs; // xs[0] = -inf
    vector<Op> ops;         // operation log for rollback

    // compute intersection x-coordinate where line l becomes better than r
    long double inter(const Line &l, const Line &r) {
        if (l.a == r.a) {
            // parallel lines: whichever has larger intercept wins everywhere
            return (l.b > r.b) ? PINF : NINF; // if l better => +inf (l dominates to +inf)
        }
        return (long double)(r.b - l.b) / (long double)(l.a - r.a);
    }

    void clear() { lines.clear(); xs.clear(); ops.clear(); }

    // add line with slope strictly greater than previous line's slope
    void add_line(const Line &ln) {
        Op op;
        op.added = true;

        if (lines.empty()) {
            // first line
            lines.push_back(ln);
            xs.push_back(NINF);
            ops.push_back(std::move(op));
            return;
        }

        // equal slope handling: if new line is never better, do nothing.
        if (ln.a == lines.back().a) {
            if (ln.b <= lines.back().b) {
                // new line worse or equal: record no-op so rollback matches calls
                op.added = false;
                ops.push_back(std::move(op));
                return;
            } else {
                // new line strictly better: remove last line (store it)
                op.removed_lines.push_back(lines.back());
                op.removed_xs.push_back(xs.back());
                lines.pop_back();
                xs.pop_back();
                if (lines.empty()) {
                    lines.push_back(ln);
                    xs.push_back(NINF);
                    ops.push_back(std::move(op));
                    return;
                }
            }
        }

        // compute intersection with current back, and pop while intersection
        // is <= previous intersection (meaning back is useless)
        long double x = inter(lines.back(), ln);
        while (!xs.empty() && x <= xs.back()) {
            // remove the last line and record it
            op.removed_lines.push_back(lines.back());
            op.removed_xs.push_back(xs.back());
            lines.pop_back();
            xs.pop_back();
            if (lines.empty()) break;
            x = inter(lines.back(), ln);
        }
        // finally add new line; its valid region starts at x
        lines.push_back(ln);
        xs.push_back(x);
        ops.push_back(std::move(op));
    }

    // query max at arbitrary x
    ll query(ll x) const {
        if (lines.empty()) return LLONG_MIN; // or some sentinel
        // find last index i with xs[i] <= x
        int l = 0, r = (int)xs.size()-1, ans = 0;
        while (l <= r) {
            int m = (l + r) >> 1;
            if (xs[m] <= (long double)x) {
                ans = m;
                l = m + 1;
            } else r = m - 1;
        }
        return lines[ans].eval(x);
    }

    // rollback last add_line() call
    bool rollback() {
        if (ops.empty()) return false;
        Op op = std::move(ops.back());
        ops.pop_back();
        if (!op.added) {
            // no-op add: nothing changed
            return true;
        }
        // remove the line we added
        if (!lines.empty()) {
            lines.pop_back();
            xs.pop_back();
        }
        // restore removed lines in reverse order
        for (int i = (int)op.removed_lines.size() - 1; i >= 0; --i) {
            lines.push_back(op.removed_lines[i]);
            xs.push_back(op.removed_xs[i]);
        }
        return true;
    }
};

RollbackableCHT cht;
int n;
vector<int> v, c;
vector<vector<pair<int, int>>> adj;

vector<int> dp;
void dfs(int node , int p = -1 , int d = 0)
{
    if(p == -1) dp[node] = 0;
    else dp[node] = cht.query(v[node]) + v[node] * d + c[node];

    cht.add_line(Line(-d , dp[node]));

    for(auto [child , len] : adj[node])
    {
        if(child == p)continue;
        dfs(child , node , d + len);
    }
    cht.rollback();
}

signed main() {
    fast;


//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);

    cin >> n;
    dp = v = c = vector<int>(n);
    adj.resize(n);

    for (int i = 0; i < n - 1; ++i) {
        int u, vv, d;
        cin >> u >> vv >> d;
        u--;
        vv--;
        adj[u].emplace_back(vv, d);
        adj[vv].emplace_back(u, d);
    }

    for (int i = 1; i < n; ++i) {
        cin >> c[i] >> v[i];
    }


    dfs(0);

    for(int i = 1 ; i < n ; i++) cout << dp[i] << " ";
    cout<<'\n';



}

• Subtask 1: 60 / 100