Submission #1263362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263362		amigoo99234	Harbingers (CEOI09_harbingers)	C++20	20 / 100	169 ms	131072 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 = 1e9 + 5, M = 1e5 + 5, K = 505;



// A line: y = m * x + c
struct Line {
    ll m, c;
    Line(ll _m = 0, ll _c = OO) : m(_m), c(_c) {}
    // safe evaluation using __int128 and clamp to avoid undefined behavior
    ll eval(ll x) const {
        __int128 val = (__int128)m * (__int128)x + (__int128)c;
        if (val > ( (__int128)LLONG_MAX / 2 )) return LLONG_MAX;
        if (val < ( (__int128)LLONG_MIN / 2 )) return LLONG_MIN;
        return (ll)val;
    }
    ll operator()(ll x) const { return eval(x); }
};

struct Node {
    Line line;
    Node* left = nullptr;
    Node* right = nullptr;
    Node(const Line &L = Line()) : line(L) {}
};

// change record (either pointer change or a line content change)
struct Change {
    bool isLineChange;
    // pointer change:
    Node** ptrAddr = nullptr;
    Node* oldPtr = nullptr;
    // line change:
    Node* node = nullptr;
    Line oldLine;
    // constructors
    Change(Node** p, Node* old) : isLineChange(false), ptrAddr(p), oldPtr(old) {}
    Change(Node* nd, const Line &oldL) : isLineChange(true), node(nd), oldLine(oldL) {}
};

vector<Change> changeLog;
vector<int> insertCheckpoints;

// record pointer change (address of the Node* variable and its old value)
inline void record_ptr(Node*& p) {
    changeLog.emplace_back(&p, p);
}

// record a node->line change
inline void record_line(Node* node) {
    changeLog.emplace_back(node, node->line);
}

void rollbackTo(int checkpoint) {
    while ((int)changeLog.size() > checkpoint) {
        Change ch = changeLog.back();
        changeLog.pop_back();
        if (!ch.isLineChange) {
            // pointer change: restore pointer
            *ch.ptrAddr = ch.oldPtr;
        } else {
            // line change: restore node->line
            ch.node->line = ch.oldLine;
        }
    }
}

void rollbackLastInsert() {
    if (!insertCheckpoints.empty()) {
        rollbackTo(insertCheckpoints.back());
        insertCheckpoints.pop_back();
    }
}

// Insert implementation (min Li Chao)
void insert_impl(Line newLine, Node*& root, ll l, ll r) {
    if (!root) {
        record_ptr(root);               // record change to this pointer
        root = new Node(newLine);
        return;
    }

    ll m = (l + r) / 2;
    bool lef = newLine.eval(l) < root->line.eval(l);
    bool mid = newLine.eval(m) < root->line.eval(m);

    if (mid) {
        record_line(root);             // record old line BEFORE swapping
        swap(root->line, newLine);
    }

    if (r - l == 1) return;

    if (lef != mid) insert_impl(newLine, root->left, l, m);
    else insert_impl(newLine, root->right, m, r);
}

// Public API for tracked insertion
void insert(Line newLine, Node*& root, ll l = -N, ll r = +N) {
    insertCheckpoints.push_back((int)changeLog.size());
    insert_impl(newLine, root, l, r);
}

// query min at x
ll query(ll x, Node* root, ll l = -N, ll r = +N) {
    if (!root) return OO;
    ll m = (l + r) / 2;
    ll res = root->line.eval(x);
    if (r - l == 1) return res;
    if (x < m) return min(res, query(x, root->left, l, m));
    else return min(res, query(x, root->right, m, r));
}


Node *root = nullptr;
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] = query(v[node] , root) + v[node] * d + c[node];

    insert(Line(-d , dp[node]) , root);

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

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: 20 / 100