Submission #1274000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274000		quocbaoo	Harbingers (CEOI09_harbingers)	C++20	100 / 100	105 ms	21428 KiB

harbingers

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
ll dp[100005],f[100005],s[100005],v[100005];pair<ll,ll> line[100005];
vector<pair<ll,ll>> g[100005];
int sz;
struct Node{
    ll fi,se;pair<ll,ll> ba;
};
deque<Node> tra;
ll get(pair<ll,ll> u1,ll z){
    return u1.fi*z+u1.se;
}
ll get_min(ll z){
    ll l=1,r=sz,ans=get(line[1],z);
    while (l<r){
        int mid=(l+r)/2;
        ll z1=get(line[mid],z),z2=get(line[mid+1],z);
        if (z1>=z2) l=mid+1;else r=mid;
        ans=min(ans,min(z1,z2));
    }
    return ans;
}
bool check(pair<ll,ll> x,pair<ll,ll> y,pair<ll,ll> z){
    return (double)(z.se-x.se)/(x.fi-z.fi)<=(double) (y.se-x.se)/(x.fi-y.fi);
}
void bodyfix(pair<ll,ll> x){
    int l=2,r=sz,ans=sz+1;
    while (l<=r){
        int mid=(l+r)/2;
        if (check(line[mid-1],line[mid],x)) ans=mid,r=mid-1;
        else l=mid+1;
    }
//    cout<<ans<<" "<<line[ans].fi<<" "<<line[ans].se<<endl;
    tra.push_back({sz,ans,line[ans]});
    sz=ans;
    line[ans]=x;
}
void dfs(int u,int pa){
    if (u!=1){
        ll z=get_min(v[u]);
        dp[u]=z+s[u]+f[u]*v[u];
        bodyfix({-f[u],dp[u]});
    }
    else{
        sz=1;line[1]={0,0};
    }
    for (auto j:g[u]){
        if (j.fi==pa) continue;
        f[j.fi]=f[u]+j.se;
        dfs(j.fi,u);
    }
    if (u==1) return ;
    Node z=tra.back();tra.pop_back();
    sz=z.fi;line[z.se]=z.ba;
}
int main(){
    if (fopen("CHT4.inp","r")){
        freopen("CHT4.inp","r",stdin);
        freopen("CHT4.out","w",stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;cin>>n;
    for (int i=1;i<n;i++){
        ll u,j,w;cin>>u>>j>>w;
        g[u].push_back({j,w});
        g[j].push_back({u,w});
    }
    for (int i=2;i<=n;i++) cin>>s[i]>>v[i];
    dfs(1,1);
    for (int i=2;i<=n;i++)cout<<dp[i]<<" ";
}

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen("CHT4.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen("CHT4.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100