Submission #1104441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104441		BF001	Harbingers (CEOI09_harbingers)	C++17	90 / 100	125 ms	37092 KiB

harbingers

#include<bits/stdc++.h>
using namespace std;
 
#define N 100005
#define oo 1e18
#define fi first 
#define se second

typedef pair<int, int> ii;



int n, ma, v[N], s[N];
long long dep[N], dp[N];

struct line{
    int a;
    line(){
        a = 0;
    }
    line(int x){
        a = x;
    }
    long long operator ()(int x){
        return (long long) -dep[a] * x + dp[a];
    }
};

line bit[4 * N]; 
stack<pair<int, line>> st;
vector<int> val;
vector<ii> adj[N];

void ud(int id, int l, int r, line nw){
    if (l == r){
        if (bit[id](val[l]) > nw(val[l])){
            st.push({id, bit[id]});
            bit[id] = nw;
        }
        return;
    }
    int mid = (l + r) >> 1;
    if (-dep[bit[id].a] > -dep[nw.a]) {st.push({id, bit[id]}); swap(bit[id], nw);}
    if (bit[id](val[mid]) > nw(val[mid])){
        st.push({id, bit[id]});
        swap(bit[id], nw);
        ud(id * 2 + 1, mid + 1, r, nw);
    }
    else ud(id * 2, l, mid, nw);
}

long long get(int id, int l, int r, int pos){
    if (l == r){
        return bit[id](pos);
    }
    int mid = (l + r) >> 1;
    if (pos <= val[mid]) return min(bit[id](pos), get(id * 2, l, mid, pos));
    else return min(bit[id](pos), get(id * 2 + 1, mid + 1, r, pos));
}

void rollback(int si){
    while ((int) st.size() > si){
        int id = st.top().fi;
        line tmp = st.top().se;
        bit[id] = tmp;
        st.pop(); 
    }
}

void dfs(int u, int p){
    if (u != 1) dp[u] = get(1, 0, ma, v[u]) + dep[u] * v[u] + s[u];
    int si = (int) st.size();
    ud(1, 0, ma, line(u));
    for (auto x : adj[u]){
        if (x.fi == p) continue;
        dep[x.fi] = dep[u] + x.se;
        dfs(x.fi, u);
    }
    rollback(si);
}

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

    dp[0] = oo;
    
    cin >> n;
    for (int i = 1; i <= n - 1; i++){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

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

    sort(val.begin(), val.end());
    val.resize(unique(val.begin(), val.end()) - val.begin());
    ma = (int) val.size() - 1;

    dfs(1, 0);
    for (int i = 2; i <= n; i++) cout << dp[i] << " ";

 
    return 0;
}

• Subtask 1: 90 / 100