Submission #1277881

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277881		harryleee	Harbingers (CEOI09_harbingers)	C++20	100 / 100	102 ms	18564 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

const int N = 100005;
const long long INFLL = (long long)4e18;

typedef pair<long long,long long> Line;

struct operation {
    int pos, top;
    Line overwrite;
    operation(int _p=0, int _t=0, Line _o = {0,0}) {
        pos = _p; top = _t; overwrite = _o;
    }
};
vector<operation> undoLst;
Line lines[N];
int n, top;

inline long long eval(const Line &line, long long x) {
    return line.X * x + line.Y;
}

// check if middle line b is unnecessary between a and c
inline bool bad(const Line &a, const Line &b, const Line &c) {
    // compare intersection(a,b) >= intersection(a,c)
    // (b.Y - a.Y)/(a.X - b.X) >= (c.Y - a.Y)/(a.X - c.X)
    // cross multiply safely with __int128
    __int128 left = (__int128)(b.Y - a.Y) * (__int128)(a.X - c.X);
    __int128 right = (__int128)(c.Y - a.Y) * (__int128)(a.X - b.X);
    return left >= right;
}

long long getMin(long long coord) {
    int l = 0, r = top - 1;
    long long ans = eval(lines[l], coord);
    while (l < r) {
        int mid = (l + r) >> 1;
        long long x = eval(lines[mid], coord);
        long long y = eval(lines[mid + 1], coord);
        if (x > y) l = mid + 1; else r = mid;
        if (x < ans) ans = x;
        if (y < ans) ans = y;
    }
    return ans;
}

bool insertLine(Line newLine) {
    int l = 1, r = top - 1, k = top;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (bad(lines[mid - 1], lines[mid], newLine)) {
            k = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    // store undo info: position k and previous top and previous content at lines[k]
    undoLst.emplace_back(k, top, lines[k]);
    top = k + 1;
    lines[k] = newLine;
    return true;
}

void undo() {
    operation ope = undoLst.back(); undoLst.pop_back();
    top = ope.top;
    lines[ope.pos] = ope.overwrite;
}

/* Problem-specific arrays */
long long f[N], S[N], V[N], d[N];
vector<pair<int,int>> a[N];

void dfs(int u, int par) {
    if (u > 1) {
        long long best = getMin(V[u]);
        f[u] = best + S[u] + V[u] * d[u];
    }
    // insert this node's line for children: y = -d[u] * x + f[u]
    insertLine({-d[u], f[u]});
    for (auto &e : a[u]) {
        int v = e.first;
        int uv = e.second;
        if (v == par) continue;
        d[v] = d[u] + uv;
        dfs(v, u);
    }
    undo();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    int u, v, c;
    for (int i = 1; i < n; ++i) {
        cin >> u >> v >> c;
        a[u].push_back({v, c});
        a[v].push_back({u, c});
    }
    // read S and V for nodes 2..n (node 1 has none)
    for (int i = 2; i <= n; ++i) cin >> S[i] >> V[i];

    // initialize hull: one dummy line at index 0 and top = 1
    top = 1;
    lines[0] = {0, INFLL}; // dummy large value so real lines will be better

    // d[1] = 0, f[1] is 0 by global init
    dfs(1, 0);

    for (int i = 2; i <= n; ++i) {
        cout << f[i] << (i==n?'\n':' ');
    }
    return 0;
}

• Subtask 1: 100 / 100