Submission #1298018

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298018		jahongir	Harbingers (CEOI09_harbingers)	C++20	100 / 100	135 ms	18284 KiB

harbingers

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")


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

#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define pb push_back
#define all(a) a.begin(),a.end()


ll isect(pll a, pll b){
    return (a.second - b.second)/(b.first - a.first);
}

const int mxn = 1e5+1;
vector<pii> g[mxn];
ll vel[mxn],cost[mxn],dp[mxn];
pll vec[mxn+5];
int cur = 1;


ll get(ll x){
    int l = 0, r = cur-1;
    while(l < r){
        int mid = (l+r)>>1;
        if(isect(vec[mid],vec[mid+1]) < x) l = mid+1;
        else r = mid;
    }
    return vec[l].first * x + vec[l].second;
}

ll lower(pll Line){
    if(cur < 2 || isect(Line,vec[cur-1]) >= isect(vec[cur-2],vec[cur-1]))
        return cur;
    int l = 1, r = cur-1;
    while(l < r){
        int mid = (l+r)>>1;
        if(isect(Line,vec[mid]) < isect(vec[mid],vec[mid-1])) r = mid;
        else l = mid+1;
    }
    return l;
}


void dfs(int u, int p, ll dep){
    dp[u] = get(vel[u]) + dep*vel[u] + cost[u];
    pll Line = {-dep,dp[u]};
    int prev_cur = cur;
    int prev_pos = cur = lower(Line);
    pll prev_line = vec[prev_pos];
    vec[cur++] = Line;

    for(auto [v,c] : g[u]) if(v!=p)
        dfs(v,u,dep+c);

    cur = prev_cur;
    vec[prev_pos] = prev_line;
}



void solve(){
    int n; cin >> n;
    for(int i = 1; i < n; i++){
        int u,v,c; cin >> u >> v >> c;
        g[u].pb({v,c}); g[v].push_back({u,c});
    }
    for(int i = 2; i <= n; i++)
        cin >> cost[i] >> vel[i];

    vec[0] = {0,0};
    
    for(auto [v,c] : g[1])
        dfs(v,1,c);

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

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    while(t--){solve();}
}

• Subtask 1: 100 / 100