Submission #738652

#	Time	Username	Problem	Language	Result	Execution time	Memory
738652		bgnbvnbv	Harbingers (CEOI09_harbingers)	C++14	70 / 100	1099 ms	26176 KiB

harbingers

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=1e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
#define line pli
using ld=long double;
ll dp[maxN];
int v[maxN];
int s[maxN];
ll h[maxN];
struct ConvexHullTrick
{
    vector<ll> dt;
    vector<ld> x;
    struct qq
    {
        ll a;
        ld b;
        bool c;
    };
    vector<qq>D;
    void rollback(ll cc)
    {
        while(D.size()>cc)
        {
            if(D.back().c==1)
            {
                dt.pop_back();
                x.pop_back();
            }
            else
            {
                dt.pb(D.back().a);
                x.pb(D.back().b);
            }
            D.pop_back();
        }
    }
    ld giao(ll l1,ll l2)
    {
        return 1. * (dp[l2] - dp[l1]) / (-h[l1] + h[l2]);
    }

    bool chk(ll l2, ll l1, ll l)
    {
        return giao(l, l1) > giao(l, l2);
    }
    void add(ll l)
    {
        while (dt.size() >= 2 && !chk(dt[dt.size() - 2], dt.back(), l))
        {
            D.pb({dt.back(),x.back(),0});
            dt.pop_back();
            x.pop_back();
        }
        if (dt.empty())
            x.pb(-inf);
        else
            x.pb(giao(l, dt.back()));
        dt.pb(l);
        D.pb({dt.back(),x.back(),1});
    }
    ll query(ll uoc)
    {
        int p = upper_bound(x.begin(), x.end(), uoc) - x.begin() - 1;
        int id=dt[p];
        return -h[id] * uoc + dp[id];
    }
}cht;

vector<pair<int,int>>g[maxN];
void dfs(ll u=1,ll p=0)
{
    dp[1]=0;
    if(u!=1)
    {
        dp[u]=cht.query(v[u])+s[u]+h[u]*v[u];
    }
    ll x=cht.D.size();
    cht.add(u);
    for(auto zz:g[u])
    {
        if(zz.fi!=p)
        {
            h[zz.fi]=h[u]+zz.se;
            dfs(zz.fi,u);
        }
    }
    cht.rollback(x);
}
ll n;;
void solve()
{
    cin >> n;
    for(int i=1;i<n;i++)
    {
        ll u,v,w;
        cin >> u >> v >> w;
        g[u].pb({v,w});
        g[v].pb({u,w});
    }
    for(int i=2;i<=n;i++)
    {
        cin >> s[i] >> v[i];
    }
    dfs();
    for(int i=2;i<=n;i++) cout << dp[i]<<' ';
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

harbingers.cpp: In member function 'void ConvexHullTrick::rollback(ll)':
harbingers.cpp:32:23: warning: comparison of integer expressions of different signedness: 'std::vector<ConvexHullTrick::qq>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   32 |         while(D.size()>cc)
      |               ~~~~~~~~^~~

• Subtask 1: 70 / 100