Submission #1193215

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193215		alexdumitru	Harbingers (CEOI09_harbingers)	C++20	100 / 100	155 ms	29412 KiB

harbingers

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>

using ll = long long;

const int MAX_N = 100000;
const ll INF = 1e15;

int n;

struct Edge {
    int to, length;
};

std::vector<Edge> g[MAX_N + 1];

struct Harbinger {
    int s, v;
} a[MAX_N + 1];

struct Line {
    ll a, b;
    ll operator() (ll x) {
        return a * x + b;
    }

    Line() : a(0), b(INF) {}
    Line(ll _a, ll _b) : a(_a), b(_b) {}
};

struct Change {
    int node;
    int l;
};

std::stack<Change> changes;

std::vector<int> viteze;

Line lines[MAX_N + 1];

struct LiChaoTree {
    int tree[4 * MAX_N + 1];
    int cnt;

    void add_line(int node, int st, int dr, int l) {
        int mij = (st + dr) / 2;
        if (lines[tree[node]](viteze[mij]) > lines[l](viteze[mij])) {
            changes.push(Change {node, tree[node]});
            std::swap(tree[node], l);
        }
        if (st == dr) return;
        if (lines[l](viteze[st]) < lines[tree[node]](viteze[st]))
            add_line(node * 2, st, mij, l);
        else add_line(node * 2 + 1, mij + 1, dr, l);
    }

    void add_line(Line l) {
        lines[++cnt] = l;
        add_line(1, 0, (int) viteze.size() - 1, cnt);
    }

    ll query(int node, int st, int dr, int pos) {
        ll ans = lines[tree[node]](viteze[pos]);
        if (st == dr)
            return ans;
        int mij = (st + dr) / 2;
        if (pos <= mij)
            ans = std::min(ans, query(node * 2, st, mij, pos));
        else ans = std::min(ans, query(node * 2 + 1, mij + 1, dr, pos));
        return ans;
    }

    ll query(int pos) {
        return query(1, 0, (int) viteze.size() - 1, pos);
    }

    void revert(int snapshot) {
        while ((int) changes.size() > snapshot) {
            Change c = changes.top();
            changes.pop();
            tree[c.node] = c.l;
        }
    }
};

ll sum_path[MAX_N + 1];

LiChaoTree tree;

ll ans[MAX_N + 1];

void dfs(int node, int dad) {
    if (node != 1)
        ans[node] = a[node].s + sum_path[node] * viteze[a[node].v] + tree.query(a[node].v);

    int snapshot = changes.size();

    tree.add_line(Line {-sum_path[node], ans[node]});

    for (auto it : g[node]) {
        if (it.to == dad) continue;

        sum_path[it.to] = sum_path[node] + it.length;

        dfs(it.to, node);
    }

    tree.revert(snapshot);
}

void solve() {
    std::cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, l;
        std::cin >> u >> v >> l;
        g[u].push_back(Edge {v, l});
        g[v].push_back(Edge {u, l});
    }

    for (int i = 2; i <= n; i++) {
        std::cin >> a[i].s >> a[i].v;
        viteze.push_back(a[i].v);
    }

    std::sort(viteze.begin(), viteze.end());
    viteze.erase(std::unique(viteze.begin(), viteze.end()), viteze.end());

    for (int i = 2; i <= n; i++) {
        a[i].v = std::lower_bound(viteze.begin(), viteze.end(), a[i].v) - viteze.begin();
    }

    dfs(1, 0);

    for (int i = 2; i <= n; i++)
        std::cout << ans[i] << ' ';
}

int main() {
    solve();
    return 0;
}

• Subtask 1: 100 / 100