Submission #1123885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123885		lftroq	Harbingers (CEOI09_harbingers)	C++20	100 / 100	97 ms	23224 KiB

harbingers

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;

const ll INF=1e15;
const ll N=1e5+5;

struct line
{
    ll a,b;
    line() {a=b=0;}
    line(ll _a,ll _b)
    {
        a=_a;
        b=_b;
    }
    ll val(ll x){return a*x+b;}
};

double inter(line a,line b)
{
    return (1.0*(b.b-a.b))/(1.0*(a.a-b.a));
}

ll n,cn;
line lines[N];
vector<pair<pii,line>> liem;
vector<pii> graph[N];
ll h[N],s[N],v[N];
ll dp[N];

void addline(line f)
{
    ll l=1,r=cn-1,temp=cn;
    while(l<=r)
    {
        ll mid=(l+r)>>1;
        if(inter(lines[mid],lines[mid-1])>=inter(lines[mid],f))
        {
            temp=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    liem.push_back({{temp,cn},lines[temp]});
    cn=temp+1;
    lines[temp]=f;
}

void rollback()
{
    lines[liem.back().fi.fi]=liem.back().se;
    cn=liem.back().fi.se;
    liem.pop_back();
}

ll get(ll x)
{
    ll l=1,r=cn-1,temp=0;
    while(l<=r)
    {
        ll mid=(l+r)>>1;
        if(inter(lines[mid],lines[mid-1])<x)
        {
            temp=mid;
            l=mid+1;
        }
        else r=mid-1;
    }
    return lines[temp].val(x);
}

void dfs_init(ll u,ll p)
{
    for(ll i=0;i<(ll)graph[u].size();i++)
    {
        ll v=graph[u][i].fi,w=graph[u][i].se;
        if(v==p) continue;
        h[v]=h[u]+w;
        dfs_init(v,u);
    }
}

void dfs(ll u,ll p)
{
    //cout << u << ' ' << p << ' ' << cn << ":" << endl;
    //for(ll i=1;i<=cn;i++) cout << lines[i].a << ' ' << lines[i].b << endl;
    //cout << "===" << endl;
    if(u!=1) dp[u]=get(v[u])+1ll*h[u]*v[u]+s[u];
    addline(line(-h[u],dp[u]));
    for(ll i=0;i<(ll)graph[u].size();i++)
    {
        ll v=graph[u][i].fi;
        if(v==p) continue;
        dfs(v,u);
    }
    rollback();
}

void solve()
{
    cin >> n;
    for(ll i=1;i<n;i++)
    {
        ll u,v,w;
        cin >> u >> v >> w;
        graph[u].push_back({v,w});
        graph[v].push_back({u,w});
    }
    for(ll i=2;i<=n;i++) cin >> s[i] >> v[i];
    dfs_init(1,1);
    dfs(1,1);
    for(ll i=2;i<=n;i++) cout << dp[i] << ' ';
    cout << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if(fopen("lftroq.inp","r"))
    {
        freopen("lftroq.inp","r",stdin);
        freopen("lftroq.out","w",stdout);
    }
    solve();
    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 100 / 100