Submission #1193150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193150		alexdumitru	Harbingers (CEOI09_harbingers)	C++20	0 / 100	4 ms	9028 KiB

harbingers

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

#define int long long

std::ifstream fin("harbingers.in");
std::ofstream fout("harbingers.out");

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 {
    ll 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;
    Line l;
};

std::stack<Change> changes;

std::vector<int> viteze;

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

    void add_line(int node, int st, int dr, Line l) {
        int mij = (st + dr) / 2;
        if (tree[node](viteze[mij]) > l(viteze[mij])) {
            changes.push(Change {node, tree[node]});
            std::swap(tree[node], l);
        }
        if (st == dr) return;
        if (l(viteze[st]) < 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) {
        add_line(1, 0, (int) viteze.size() - 1, l);
    }

    ll query(int node, int st, int dr, int pos) {
        ll ans = 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 (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() {
    fin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, l;
        fin >> u >> v >> l;
        g[u].push_back(Edge {v, l});
        g[v].push_back(Edge {u, l});
    }

    for (int i = 2; i <= n; i++) {
        fin >> 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++)
        fout << ans[i] << ' ';
}

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

• Subtask 1: 0 / 100