Submission #993588

#	Time	Username	Problem	Language	Result	Execution time	Memory
993588		efishel	Harbingers (CEOI09_harbingers)	C++17	20 / 100	114 ms	65536 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector <ll>;
using ii = pair <ll, ll>;

const ll MAXN = 1E5+16, INF = ll(1E18)+16;
vector <pair <int, int> > adj[MAXN];
ll dp[MAXN];
int dis[MAXN];
int sleep[MAXN], slow[MAXN];

const ii maxf = {0, INF};
struct LiChao{
    int ind=0, L, R;
    vector<int> left, right;
    vector<ii> line;
    LiChao(int L, int R): L(L), R(R), left(MAXN,-1), right(MAXN,-1), line(MAXN,maxf){}
    ll eval(ii a, ll x) {return a.first*x+a.second;}
    void update(ii ln, vector <vector <pair <int, ii> > > &ups){
        int u=0, l=L, r=R, mid;
        while(true){
            mid=(l+r)>>1;
            if(eval(line[u],mid) > eval(ln,mid)) {
                swap(line[u],ln);
                ups.back().push_back({u, ln});
            }
            if(ln==maxf || l==r) return;
            if(eval(line[u],l) < eval(ln,l)) l = mid+1, u=(right[u] == -1 ? right[u] = ++ind : right[u]);
            else r=mid, u=(left[u] == -1 ? left[u] = ++ind : left[u]);
        }
    }
    ll query(int x){
        ll ans=INF;
        int u=0, l=L, r=R, mid;
        while(true){
            mid=(l+r)>>1;
            ans=min(ans,eval(line[u],x));
            if(l==r) return ans;
            if(x>mid && right[u]!=-1) l=mid+1, u=right[u];
            else if(x<=mid && left[u]!=-1) r=mid, u=left[u];
            else return ans;
        }
    }
} st(0, 1E9);

vector <vector <pair <int, ii> > > ups;

void rollback () {
    auto th = ups.back(); ups.pop_back();
    for (auto [stPtr, lastFun] : th) {
        st.line[stPtr] = lastFun;
    }
}

void dfs (ll u, ll par) {
    dp[u] = ll(sleep[u])+ll(slow[u])*dis[u];
    dp[u] = min(dp[u], st.query(slow[u])  +ll(sleep[u])+ll(slow[u])*dis[u]);
    ups.push_back({});
    st.update({-dis[u], dp[u]}, ups);
    for (auto [v, w] : adj[u]) {
        if (v == par) continue;
        dis[v] = dis[u]+w;
        dfs(v, u);
    }
    rollback();
}

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n;
    cin >> n;
    for (ll i = 1; i < n; i++) {
        ll u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
    }
    for (ll i = 1; i < n; i++) cin >> sleep[i] >> slow[i];
    dis[0] = 0;
    dp[0] = 0;
    dfs(0, 0);
    for (ll i = 1; i < n; i++) cout << dp[i] << ' ';
    cout << '\n';
    return 0;
}

• Subtask 1: 20 / 100