Submission #1122606

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122606		urosk	Harbingers (CEOI09_harbingers)	C++20	60 / 100	130 ms	36944 KiB

harbingers

#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;
using ld = double;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

#define mod 1
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
    a = add(a,0);
    b = add(b,0);
    ll ans = (a*b)%mod;
    if(ans<0) ans+=mod;
    return ans;
}


const ll maxn = 100005;
const ll lg = 18;
ll n;
vector<pll> g[maxn];
ll dub[maxn];
pll a[maxn];
ll dp[maxn];
#define pld array<ld,3>
ld f(pld a,pld b) {
    return (a[1]-b[1])/(b[0]-a[0]);
}

pld stk[maxn];
ll up[lg][maxn];
ll id[maxn],tsz = 0;
void dfs(ll u,ll p) {
    for(pll q : g[u]) {
        ll s = q.fi,w = q.sc;
        if(s==p) continue;
        dub[s] = dub[u] + w;
        id[s] = ++tsz;
        up[0][tsz] = id[u];
        for(ll j = 1;j<lg;j++) up[j][tsz] = up[j-1][up[j-1][tsz]];
        ll cur = tsz;
        for(ll j = lg-1;j>=0;j--) {
            if(a[s].sc<stk[up[j][cur]][2]) cur = up[j][cur];
        }
        cur = up[0][cur];
        dp[s] = a[s].fi + a[s].sc*dub[s] + stk[cur][0]*a[s].sc + stk[cur][1];
        stk[tsz] = {-dub[s]*1.0,dp[s]*1.0,1.0*llinf};
        cur = tsz;
        for(ll j = lg-1;j>=0;j--) {
            ld cx = f(stk[up[j][cur]],stk[tsz]);
            if(cx<=stk[up[j][cur]][2])  cur = up[j][cur];
        }
        cur = up[0][cur];
        ld cx = f(stk[cur],stk[tsz]);
        stk[tsz] = {-dub[s]*1.0,dp[s]*1.0,cx};
        up[0][tsz] = cur;
        for(ll j = 1;j<lg;j++) up[j][tsz] = up[j-1][up[j-1][tsz]];
        dfs(s,u);
    }
}
void tc(){
    cerr<<fixed<<setprecision(12);
    cin >> n;
    for(ll i = 1;i<=n-1;i++) {
        ll x,y,d; cin >> x >> y >> d;
        g[x].pb({y,d});
        g[y].pb({x,d});
    }
    for(ll i = 2;i<=n;i++) cin >> a[i].fi >> a[i].sc;
    dp[1] = 0;
    id[1] = 0;
    stk[0] = {0,0,-llinf};
    dfs(1,1);
    for(ll i = 2;i<=n;i++) cout<<dp[i]<< " ";
    cout<<endl;
}

int main(){
    ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    int t; t = 1;
    while(t--){
        tc();
    }
    return (0-0);
}

• Subtask 1: 60 / 100