Submission #1273731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273731		quocbaoo	Harbingers (CEOI09_harbingers)	C++20	0 / 100	132 ms	131072 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];
deque<int> st;
double doc(int i,int j){
//    cout<<f[i]<<" "<<f[j]<<endl;
    return (double) (dp[j]-dp[i])/double(f[j]-f[i]);
}
void dfs(int u,int pa){
    deque<int> lu,nho;
    while (st.size()>1){
        pair<ll,ll> i=line[st[0]],j=line[st[1]];
        if ((j.se-i.se)<=v[u]*(-j.fi+i.fi)) {
            lu.push_back(st[0]),st.pop_front();
        }
        else break;
    }
    if (u!=1){
        pair<ll,ll> i=line[st[0]];
        dp[u]=i.fi*v[u]+i.se+s[u]+f[u]*v[u];line[u]={-f[u],dp[u]};
        while (st.size()>1){
            if (doc(st[st.size()-2],st.back())>=doc(st.back(),u)){
                nho.push_back(st.back());st.pop_back();
            }
            else break;
        }
        st.push_back(u);
    }
    else{
        st.push_back(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);
    }
    st.pop_back();
    while (!lu.empty()){
        st.push_front(lu.back());lu.pop_back();
    }
    while (!nho.empty()){
        st.push_back(nho.back());nho.pop_back();
    }
}
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:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         freopen("CHT4.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen("CHT4.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100