Submission #1335104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1335104		yousefOsama06	Harbingers (CEOI09_harbingers)	C++20	20 / 100	165 ms	131072 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define ll long long
#define ld long double
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ones(n) __builtin_popcountll(n)
#define msb(n) (63 - __builtin_clzll(n))
#define lsb(n) __builtin_ctzll(n)

constexpr int N = 1e5 + 5, M = 1e3 + 5, LOG = 31;
constexpr int inf = 0x3f3f3f3f;
constexpr ll llinf = 0x3f3f3f3f3f3f3f3f;
constexpr int MOD = 1e9 + 7;
constexpr double eps = 1e-9, PI = acos(-1);

const ll maxN = 1e7 + 5;

struct Line {
    ll m, c;

    Line() : m(0), c(llinf) {
    }

    Line(ll m, ll c) : m(m), c(c) {
    }
};

ll sub(ll x, Line l) {
    return x * l.m + l.c;
}

// Persistent Li Chao
struct Node {
    // range I am responsible for
    Line line;
    Node *left, *right;

    Node() {
        left = right = NULL;
    }

    Node(ll m, ll c) {
        line = Line(m, c);
        left = right = NULL;
    }

    void extend(int l, int r) {
        if (left == NULL && l != r) {
            left = new Node();
            right = new Node();
        }
    }

    Node* copy(Node* node) {
        Node* newNode = new Node;
        newNode->left = node->left;
        newNode->right = node->right;
        newNode->line = node->line;
        return newNode;
    }

    Node* add(Line toAdd, int l, int r) {
        int mid = (l + r) / 2;
        Node* cur = copy(this);
        if (l == r) {
            if (sub(l, toAdd) < sub(l, cur->line))
                swap(toAdd, cur->line);
            return cur;
        }
        bool lef = sub(l, toAdd) < sub(l, cur->line);
        bool midE = sub(mid + 1, toAdd) < sub(mid + 1, cur->line);
        if (midE)
            swap(cur->line, toAdd);
        cur->extend(l, r);
        if (lef != midE) {
            cur->left = cur->left->add(toAdd, l, mid);
        }
        else {
            if (mid + 1 > r)
                return cur;
            cur->right = cur->right->add(toAdd, mid + 1, r);
        }
        return cur;
    }

    Node* add(Line toAdd) {
        return add(toAdd, -maxN + 1, maxN - 1);
    }

    ll query(ll x, int l, int r) {
        int mid = (l + r) / 2;
        if (l == r || left == NULL)
            return sub(x, line);
        extend(l, r);
        if (x <= mid)
            return min(sub(x, line), left->query(x, l, mid));
        else
            return min(sub(x, line), right->query(x, mid + 1, r));
    }

    ll query(ll x) {
        return query(x, -maxN + 1, maxN - 1);
    }

    void clear() {
        if (left != NULL) {
            left->clear();
            right->clear();
        }
        delete this;
    }
};

Node* tree[N];
int s[N], v[N];
ll dp[N];
vector<pair<int, int>> adj[N];

void dfs(int u, int p, ll dist) {
    if (u != 1) {
        dp[u] = tree[u]->query(v[u]);
        dp[u] += dist * v[u] + s[u];
    }
    for (auto [v, w] : adj[u]) {
        if (v == p)
            continue;
        tree[v] = tree[u]->add({-dist, dp[u]});
        dfs(v, u, dist + w);
    }
}

void testCase() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v, d;
        cin >> u >> v >> d;
        adj[u].eb(v, d);
        adj[v].eb(u, d);
    }
    for (int i = 2; i <= n; i++)
        cin >> s[i] >> v[i];
    tree[1] = new Node(0, 0);
    dfs(1, 1, 0);
    for (int i = 2; i <= n; i++)
        cout << dp[i] << ' ';
}


void preCompute() {
}

int32_t main() {
#ifdef C_Lion
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("errors.txt", "w", stderr);
#else
    // freopen("harbingers.in", "r", stdin);
    // freopen("harbingers.out", "w", stdout);
#endif

    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    cout << fixed << setprecision(static_cast<int32_t>(-log10(eps)));
    preCompute();

    int tc = 1;
    // cin >> tc;
    for (int TC = 1; TC <= tc; TC++) {
        // cout << "Case #" << TC << ": ";
        testCase();
    }
}

/*




*/

• Subtask 1: 20 / 100