Submission #1288969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288969		Newtonabc	Harbingers (CEOI09_harbingers)	C++20	100 / 100	140 ms	21160 KiB

harbingers

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
int cnt=0;
ll dp[N],d[N],vl[N],s[N];
vector<pair<int,ll>> adj[N];
struct line{
    ll m,c;
    double cut(line b){return (double)(b.c-c)/(double)(m-b.m);}
    double val(ll x){return m*x+c;}
}st[N];
bool bad(line a,line b,line c){return c.cut(a)>=c.cut(b);}
ll query(ll x){
    int l=0,r=cnt-1;
    while(l<r){
        int mid=(l+r+1)/2;
        if(st[mid].cut(st[mid-1])<=x) l=mid;
        else r=mid-1;
    }
    return st[l].val(x);
}
int ins(line li){
    int l=1,r=cnt-1;
    if(cnt<2 || !bad(st[cnt-2],st[cnt-1],li)) return cnt;
    while(l<r){
        int mid=(l+r)/2;
        if(bad(st[mid-1],st[mid],li)) r=mid;
        else l=mid+1;
    }
    return l;
}
void dfs(int u,int p){
    int pi,pcnt;
    line pl;
    dp[u]=s[u]+d[u]*vl[u]+query(vl[u]);
    line l={-d[u],dp[u]};
    pi=ins(l);
    pl=st[pi];
    pcnt=cnt;
    st[pi]=l;
    cnt=pi+1;
    //cout<<u <<"\n";
    //for(int i=0;i<cnt;i++) cout<<st[i].m <<" " <<st[i].c <<"\n";
    for(auto [v,w]:adj[u]){
        if(v==p) continue;
        d[v]=d[u]+w;
        dfs(v,u);
    }
    cnt=pcnt;
    st[pi]=pl;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n-1;i++){
        int u,v;
        ll 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] >>vl[i];
    dfs(1,1);
    for(int i=2;i<=n;i++) cout<<dp[i] <<" ";
}

• Subtask 1: 100 / 100