Submission #1310511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310511		buzdi	Harbingers (CEOI09_harbingers)	C++17	100 / 100	75 ms	30512 KiB

harbingers

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int NMAX = 1e5;
const int INFx = 1e9;
const ll INF = 1e18;

int n;
ll dp[NMAX + 1];
int sp[NMAX + 1];
int st[NMAX + 1], v[NMAX + 1];
vector<pair<int, int>> g[NMAX + 1];

struct Line {
    int a;
    ll b;
    Line() : a(0), b(INF) {}
    Line(ll a, ll b) : a(a), b(b) {}
    ll eval(int x) {
        return (ll) a * x + b;
    }
};
struct Node {
    Line line;
    int left = -1, right = -1;
};

struct LiChao {
    int xmin, xmax;
    vector<Node> aint;
    stack<pair<int, Line>> st;

    int create_node() {
        aint.push_back(Node());
        return aint.size() - 1;
    }

    void init(int xmin, int xmax) {
        this->xmin = xmin;
        this->xmax = xmax;
        create_node();
    }

    pair<int, int> add_line(int node, int left, int right, Line new_line) {
        if(node == -1) {
            node = create_node();
        }

        int mid = (left + right) / 2;
        int cnt = 0;
        bool left_sign = new_line.eval(left) < aint[node].line.eval(left);
        bool mid_sign = new_line.eval(mid) < aint[node].line.eval(mid);
        bool right_sign = new_line.eval(right) < aint[node].line.eval(right);
        if(mid_sign) {
            cnt++;
            st.push({node, aint[node].line});
            swap(aint[node].line, new_line);
        }

        if(left == right) {
            return {node, cnt};
        }
        if(left_sign != mid_sign) {
            pair<int, int> left_node = add_line(aint[node].left, left, mid, new_line);
            aint[node].left = left_node.first;
            cnt += left_node.second;
        }
        else if(mid_sign != right_sign) {
            pair<int, int> right_node = add_line(aint[node].right, mid + 1, right, new_line);
            aint[node].right = right_node.first;
            cnt += right_node.second;
        }
        return {node, cnt};
    }

    ll query_min(int node, int left, int right, int x) {
        if(node == -1) {
            return INF;
        }
        if(left == right) {
            return aint[node].line.eval(x);
        }
        int mid = (left + right) / 2;
        if(x <= mid) {
            return min(aint[node].line.eval(x), query_min(aint[node].left, left, mid, x));
        }
        return min(aint[node].line.eval(x), query_min(aint[node].right, mid + 1, right, x));
    }

    int add_line(Line line) {
        return add_line(0, xmin, xmax, line).second;
    }
    ll query_min(int x) {
        return query_min(0, xmin, xmax, x);
    }
    void rollback(int k) {
        assert(k <= st.size());
        while(k--) {
            auto [node, line] = st.top();
            st.pop();
            aint[node].line = line;
        }
    }
}li_chao;

//ll get_dp(int node) {
//    ll mini = INF;
//    int dad = parent[node];
//    while(dad != 0) {
//        mini = min(mini, dp[dad] - sp[dad] * v[node]);
//        dad = parent[dad];
//    }
//    return st[node] + sp[node] * v[node] + mini;
//}

void DFS(int node, int dad = 0) {
    if(node != 1) {
        dp[node] = st[node] + (ll) sp[node] * v[node] + li_chao.query_min(v[node]);
    }
    int cnt = li_chao.add_line(Line(-sp[node], dp[node]));
    for(auto [next_node, c] : g[node]) {
        if(next_node != dad) {
            sp[next_node] = sp[node] + c;
            DFS(next_node, node);
        }
    }
    li_chao.rollback(cnt);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
        g[b].push_back({a, c});
    }
    for(int i = 2; i <= n; i++) {
        cin >> st[i] >> v[i];
    }

    int min_v = *min_element(v + 1, v + n + 1);
    int max_v = *max_element(v + 1, v + n + 1);
    li_chao.init(min_v, max_v);
    DFS(1);
    for(int i = 2; i <= n; i++) {
        cout << dp[i] << ' ';
    }
    return 0;
}

• Subtask 1: 100 / 100