Submission #580787

#	Time	Username	Problem	Language	Result	Execution time	Memory
580787		danikoynov	Harbingers (CEOI09_harbingers)	C++14	100 / 100	157 ms	22748 KiB

harbingers

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
const int maxn = 1e5 + 10;

int n;
ll depth[maxn], dp[maxn], to_start[maxn], spd[maxn];
vector < pair < int, ll > > g[maxn];

void add_edge(int v, int u, ll d)
{
    g[v].push_back({u, d});
    g[u].push_back({v, d});
}

const double inf = 1e18;
struct line
{
    ll k, m; /// k * x + m

    line(ll _k = 0, ll _m = 0)
    {
        k = _k;
        m = _m;
    }

};
    double intersect(const line &l1, const line &l2)
    {
        if (l1.k == l2.k)
        {
            if (l1.m > l2.m)
                return inf;
            return - inf;
        }
        return (double)(l2.m - l1.m) / (double)(l1.k - l2.k);
    }

struct bunch
{
    line bh;
    int res_sz;
};

line st[maxn];
int sz;

bunch add_line(ll k, ll m)
{
    line l(k, m);
    bunch cur;
    cur.res_sz = sz;
    int lf = 1, rf = sz - 1;
    while(lf <= rf)
    {
        int m = (lf + rf) / 2;
        if (intersect(st[m], l) <= intersect(st[m], st[m + 1]))
            rf = m - 1;
        else
            lf = m + 1;
    }
    sz = lf;
    ///while(sz > 1 &&  intersect(st[sz - 1], l) <= intersect(st[sz - 1], st[sz]))
    ///{
/// sz --;
    ///}
        cur.bh = st[sz + 1];
    st[++ sz] = l;

    return cur;
}

void restore_line(bunch cur)
{

    st[sz] = cur.bh;

    sz = cur.res_sz;
}

ll query(ll x)
{
    /**ll best = inf;
    for (int i = 1; i <= sz; i ++)
    {
        ll cur = st[i].k * x + st[i].m;
        if (cur < best)
            best = cur;
    }
    return best;*/
    int l = 1, r = sz - 1;
    while(l <= r)
    {
        int m = (l + r) / 2;
        if (intersect(st[m], st[m + 1]) <= (double)(x))
            l = m + 1;
        else
            r = m - 1;
    }
    return st[l].k * x + st[l].m;
}

void dfs(int v, int p)
{
    if (v != 1)
    {
        /// calculate answer
        dp[v] = depth[v] * spd[v] + to_start[v] + query(spd[v]);
    }

    /// add line

    bunch cur = add_line(- depth[v], + dp[v]);

    for (pair < int, ll > nb : g[v])
    {
        if (nb.first == p)
            continue;
        depth[nb.first] = depth[v] + nb.second;
        dfs(nb.first, v);
    }

    /// restore lines
    restore_line(cur);

}
void solve()
{
    cin >> n;
    for (int i = 1; i < n; i ++)
    {
        int v, u, d;
        cin >> v >> u >> d;
        add_edge(v, u, d);
    }
    for (int i = 2; i <= n; i ++)
        cin >> to_start[i] >> spd[i];

    dfs(1, - 1);

    for (int i = 2; i <= n; i ++)
        cout << dp[i] << " ";
    cout << endl;
}

int main()
{
    speed();
    solve();
    return 0;
}

• Subtask 1: 100 / 100