Submission #1148150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148150		garam1732	Harbingers (CEOI09_harbingers)	C++20	50 / 100	125 ms	64116 KiB

harbingers

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

#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;

const int MAXN = 100100*1;
const ll MOD = 1e9+7;
const ll INF = 2e9;

vector<pi> adj[MAXN];
ll S[MAXN], V[MAXN];
ll dst[MAXN], dp[MAXN];

struct Lichao {
    struct Line {
        ll a, b;

        ll get(ll x) {
            return a*x+b;
        }
    };
    
    struct Node {
        int l, r; Line line;
    };

    vector<Node> tree;
    Node base = {0, 0, {0, LLONG_MAX}}; 
    int root[MAXN];

    void init() {
        root[1] = 1;
        tree.push_back(base); tree.push_back({0, 0, {0, 0}});
    }

    void update(int pv, int node, ll s, ll e, Line line) {
        Line low = tree[node].line, high = line;

        if(low.get(s) > high.get(s)) swap(low, high);

        if(low.get(e) <= high.get(e)) {
            tree[node].line = low; return;
        }

        ll mid = s+e>>1;
        if(low.get(mid) >= high.get(mid)) {
            tree[node].line = high;

            tree[node].l = tree.size();
            tree.push_back(tree[tree[pv].l]);
            update(tree[pv].l, tree[node].l, s, mid, low);
        } else {
            tree[node].line = low;

            tree[node].r = tree.size();
            tree.push_back(tree[tree[pv].r]);
            update(tree[pv].r, tree[node].r, mid+1, e, high);
        }
    }

    ll solve(int node, ll s, ll e, ll x) {
        if(node == 0) return LLONG_MAX;

        ll mid=s+e>>1; ll res = tree[node].line.get(x);
        if(x <= mid) res = min(res, solve(tree[node].l, s, mid, x));
        else res = min(res, solve(tree[node].r, mid+1, e, x));

        return res;
    }
}lichao;

void dfs(int here, int par) {
    for(auto [there,w]:adj[here]) {
        if(there==par) continue;

        dst[there] = dst[here]+w;
        dfs(there, here);
    }
}

void solve(int here, int par) {
    for(auto [there,w] : adj[here]) {
        if(there==par) continue;

        dp[there] = S[there]+V[there]*dst[there] + lichao.solve(lichao.root[here], 0, INF, V[there]);
        lichao.root[there] = lichao.tree.size(); lichao.tree.push_back(lichao.tree[lichao.root[here]]);
        lichao.update(lichao.root[here], lichao.root[there], 0, INF, {-dst[there], dp[there]});
        solve(there, here);
    }
}

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

    int n; cin>>n;
    for(int i=1; i<n; i++) {
        int a, b, c; cin>>a>>b>>c;
        adj[a].push_back(pi(b,c));
        adj[b].push_back(pi(a,c));
    }

    for(int i=2; i<=n; i++) cin>>S[i]>>V[i];

    dfs(1, 1);

    dp[1] = 0; lichao.init();
    solve(1, 1);

    for(int i=2; i<=n; i++) cout<<dp[i]<<bl;
}

• Subtask 1: 50 / 100