Submission #170079

#	Time	Username	Problem	Language	Result	Execution time	Memory
170079		gs18103	Harbingers (CEOI09_harbingers)	C++14	20 / 100	264 ms	65540 KiB

harbingers

#include <bits/stdc++.h>  
#define fi first  
#define se second  
#define eb emplace_back  
#define em emplace  
#define all(v) v.begin(), v.end()  
  
using namespace std;  
typedef long long ll;  
typedef pair <int, int> pii;  
typedef pair <ll, ll> pll;  
  
const int MAX = 101010;  
const int INF = 1 << 30;  
const ll LINF = 1LL << 60;  
  
struct node {  
    int l, r; pll val;  
    node(int l, int r, pll val) : l(l), r(r), val(val) {}  
};  
vector <node> tree;  
vector <pii> g[MAX];  
int root[MAX];  
ll d[MAX];  
ll s[MAX], v[MAX], dp[MAX];  
  
ll f(pll l, ll x) {  
    return l.fi * x + l.se;  
}  
  
void expand_tree(int s, int e, pll val, int cnd, int pnd) {  
    int m = (s + e) / 2;  
    tree[cnd].val = tree[pnd].val;  
    bool left = f(val, s) < f(tree[cnd].val, s);  
    bool mid = f(val, m) < f(tree[cnd].val, m);  
    if(mid) swap(tree[cnd].val, val);  
    if(e == s + 1) return;  
    if(mid == left) {  
        tree[cnd].l = tree[pnd].l;  
        tree[cnd].r = tree.size();  
        tree.eb(0, 0, make_pair(0LL, 0LL));  
        expand_tree(m, e, val, tree[cnd].r, tree[pnd].r);  
    }  
    else {  
        tree[cnd].r = tree[pnd].r;  
        tree[cnd].l = tree.size();  
        tree.eb(0, 0, make_pair(0LL, 0LL));  
        expand_tree(s, m, val, tree[cnd].l, tree[pnd].l);  
    }  
}  
  
ll cal(int node, int s, int e, ll x) {  
    int m = (s + e) / 2;  
    if(e == s + 1) return f(tree[node].val, x);  
    if(x < m) return min(f(tree[node].val, x), cal(tree[node].l, s, m, x));  
    else return min(f(tree[node].val, x), cal(tree[node].r, m, e, x));  
}  
  
void dfs(int x, int pa) {  
    dp[x] = cal(root[pa], 1, INF, v[x]) + s[x] + v[x] * d[x];  
    root[x] = tree.size();  
    tree.eb(0, 0, make_pair(0, 0));  
    expand_tree(1, INF, make_pair(-d[x], dp[x]), root[x], root[pa]);  
    for(auto i : g[x]) {  
        if(i.fi == pa) continue;  
        d[i.fi] = d[x] + i.se;  
        dfs(i.fi, x);  
    }  
}  
  
int main() {  
    ios::sync_with_stdio(false); cin.tie(0);  
    int n;  
    cin >> n;  
    for(int i = 1; i < n; i++) {  
        int u, v, w; cin >> u >> v >> w;  
        g[u].eb(v, w), g[v].eb(u, w);  
    }  
    for(int i = 2; i <= n; i++) {  
        cin >> s[i] >> v[i];  
    }  
    tree.eb(0, 0, make_pair(0LL, 0LL));  
    for(auto i : g[1]) {  
        d[i.fi] = i.se;  
        dfs(i.fi, 1);  
    }  
    for(int i = 2; i <= n; i++) {  
        cout << dp[i] << ' ';  
    }  
}  

• Subtask 1: 20 / 100