Submission #1263191

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263191		amigoo99234	Harbingers (CEOI09_harbingers)	C++20	50 / 100	1093 ms	48460 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;

// rollback-capable LineContainer
struct Line {
    mutable ll k, m, p;
    bool operator<(const Line &o) const { return k < o.k; }
    bool operator<(ll x) const { return p < x; }
};

struct RollbackLineContainer : multiset<Line, less<>> {
    static const ll inf = LLONG_MAX;
    bool isMn = true;

    // low-level op types for rollback logging
    enum OpType { OP_INSERT, OP_ERASE, OP_SETP };
    struct Op {
        OpType type;
        Line ln; // a copy of the affected line (stores old p for SETP)
    };

    // history of operations (each add produces a vector<Op>)
    vector<vector<Op>> history;

    // integer division floor for negatives like in original code
    ll divll(ll a, ll b) {
        return a / b - ((a ^ b) < 0 && a % b);
    }

    // helper: set p of an element (Line::p is mutable so can be changed even though element is "const")
    void set_p(iterator it, ll newp) {
        // mutate the mutable member
        const_cast<ll&>(it->p) = newp;
    }

    // helper: find an element with exactly same (k,m). returns end() if not found.
    iterator find_same(const Line &target) {
        // use lower_bound(Line) which compares by k (operator<(Line))
        auto it = lower_bound(target);
        for (; it != end() && it->k == target.k; ++it) {
            if (it->m == target.m) return it;
        }
        return end();
    }

    // erase with logging: log the erased copy then erase and return iterator to next element
    iterator erase_with_log(iterator it, vector<Op> &ops) {
        ops.push_back({OP_ERASE, *it});      // save copy before erasing
        return erase(it);
    }

    // isect with logging: will record a SETP op (old copy) before changing x->p
    // returns same boolean as original isect
    bool isect_log(iterator x, iterator y, vector<Op> &ops) {
        if (y == end()) {
            if (x->p != inf) ops.push_back({OP_SETP, *x});
            set_p(x, inf);
            return false;
        }
        if (x->k == y->k) {
            ll newp = (x->m > y->m ? inf : -inf);
            if (x->p != newp) ops.push_back({OP_SETP, *x});
            set_p(x, newp);
        } else {
            ll newp = divll(y->m - x->m, x->k - y->k);
            if (x->p != newp) ops.push_back({OP_SETP, *x});
            set_p(x, newp);
        }
        return x->p >= y->p;
    }

    // add as before but log all low-level changes into a vector<Op> and push it to history
    void add(ll k, ll m) {
        vector<Op> ops; ops.reserve(8); // small reservation to reduce reallocation

        if (isMn) { k = -k; m = -m; }

        // insert new line (p will be fixed by isect calls)
        auto z = insert({k, m, 0});
        ops.push_back({OP_INSERT, *z}); // remember insertion (copy)

        auto y = z++;
        auto x = y;

        while (isect_log(y, z, ops)) z = erase_with_log(z, ops);

        if (x != begin() && isect_log(--x, y, ops)) {
            // if isect(--x,y) true then we must erase y and re-isect the new predecessor
            y = erase_with_log(y, ops);
            isect_log(x, y, ops);
        }

        while ((y = x) != begin()) {
            --x;
            if (x->p >= y->p) {
                // erase y (log it) and re-evaluate intersection on x
                auto nxt = erase_with_log(y, ops);
                isect_log(x, nxt, ops);
            } else break;
        }

        history.push_back(move(ops));
    }

    // query unchanged
    ll query(ll x) {
        auto l = *lower_bound(x);
        return (isMn ? -1 : 1) * (l.k * x + l.m);
    }

    // rollback the last add (revert logged ops in reverse order)
    void rollback() {
        if (history.empty()) return;
        auto ops = move(history.back());
        history.pop_back();

        // revert in reverse order
        for (auto it = ops.rbegin(); it != ops.rend(); ++it) {
            switch (it->type) {
                case OP_ERASE:
                    // inverse of erase is insert the stored copy back
                    insert(it->ln);
                    break;
                case OP_SETP: {
                    // inverse of set-p: find the element with same (k,m) and restore old p
                    auto found = find_same(it->ln);
                    if (found != end()) set_p(found, it->ln.p);
                    break;
                }
                case OP_INSERT: {
                    // inverse of insert is remove the inserted line (find by k,m)
                    auto found = find_same(it->ln);
                    if (found != end()) erase(found);
                    break;
                }
            }
        }
    }

    // rollback last t adds (if t > history.size() we rollback everything)
    void rollback_n(size_t t) {
        while (t-- && !history.empty()) rollback();
    }

    // clear history (forget ability to rollback)
    void clear_history() {
        history.clear();
    }
};


RollbackLineContainer 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(-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: 50 / 100