Submission #402576

#	Time	Username	Problem	Language	Result	Execution time	Memory
402576		blue	Harbingers (CEOI09_harbingers)	C++17	0 / 100	455 ms	42580 KiB

harbingers

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

/*
Let anc[u][x] be the x'th ancestor of u.
dp[u] =def= amount of time needed for message to be delivered from u to 1.

dp[1] =def= 0
dp[u] = min{S[u] + V[u]*dist(u, v) + dp[v] | v in anc[u]}
      = min{S[u] + V[u]*(dist1[u] - dist1[v]) + dp[v] | v in anc[u]}

dp[u] min= S[u] + V[u]*dist1[u]   +   -dist1[v]*V[u] + dp[v]
                                            a * x   +  b
*/
long long INF = 2'000'000'000'000'000'000;

vector<long long> edge[100001], dist[100001]; //edges, weights of edges
vector<long long> S(100001, 0), V(100001, 0); //starting time, reciprocal speed

vector<long long> dist1(100001, 0);
long long cht_anc[100001][19];
vector<long long> prev_node(100001);
vector<long long> prev_dist(100001);

void dfs1(long long u)
{
    for(long long i = 0; i < edge[u].size(); i++)
    {
        long long v = edge[u][i];
        long long d = dist[u][i];

        if(prev_node[u] == v) continue;
        prev_node[v] = u;
        prev_dist[v] = d;
        dist1[v] = dist1[u] + prev_dist[v];

        dfs1(v);
    }
}


vector<long long> a(100001), b(100001);
vector<long long> dp(100001);

// long long a(long long u)
// {
//     return -dist1[u];
// }
//
// long long b(long long u)
// {
//     return dp[u];
// }

bool intersect_comp(long long e1, long long e2, long long x)
{ /*a[e1]*x + b[e1] = a[e2]*x + b[e2]
    x_e = (b[e2] - b[e1])/(a[e1] - a[e2])
    */
    // cerr << "intersect comp " << e1 << ' ' << e2 << ' ' << double(b[e2] - b[e1])/double(a[e1] - a[e2]) << ' ' << x << ' ' << ((b[e2] - b[e1]) < (a[e1] - a[e2])*x) << '\n';
    return (b[e2] - b[e1]) <= (a[e1] - a[e2])*x; //Be very careful with the sign.
}

bool line_intersect_comp(long long e1, long long e2, long long f1, long long f2)
{//intersect(e1, e2) < intersect(f1, f2)
    // if(e2 == 1) return 1;
    return (b[e2] - b[e1])*(a[f1] - a[f2]) <= (b[f2] - b[f1])*(a[e1] - a[e2]);
}

/*
i, i+1, L
Line i+2 is a good insertion if intersect(i, i+1) < intersect(i+1, i+2)
We need to binary search for the largest line i such that intersect(i-1, i) < intersect(i, L)
*/

void dfs2(long long u)
{
    for(long long v: edge[u])
    {
        if(prev_node[u] == v) continue;

        /*w is the ideal harbinger for the harbinger from v to go to
        Using binary lifting, we search for the edge on which f(x) is maximised

        Let the lines of the ancestors of v, starting from 1 be l1, l2, ... l_q
        We are finding the value of V[v]
        We want to find some line i such that intsec(l[i-1], l[i]) <= x <= intsec(l[i], l[i+1])

        We want to find the ancestor of highest depth i such that intsec(p[i], i) > V[v]
        */
        cht_anc[v][0] = u;
        for(long long e = 1; e <= 18; e++)
            cht_anc[v][e] = cht_anc[ cht_anc[v][e-1] ][e-1];

        long long w = v;
        for(long long e = 18; e >= 0; e--)
        {
            long long temp = cht_anc[w][e];
            if(intersect_comp(prev_node[temp], temp, V[v]) == 0)
                w = temp;
        }

        while(intersect_comp(prev_node[w], w, V[v]) == 0)
            w = prev_node[w];

        dp[v] = S[v] + V[v]*dist1[v] + a[w]*V[v] + dp[w];

        a[v] = -dist1[v];
        b[v] = dp[v]; //*
        // cerr << a[v] << "*x + " << b[v] << "\n";

        // cout << v << "( " << V[v] << ") <- " << w << '\n';

        /*
        We want to find the ancestor of highest depth i such that
            intsec(p[i], i) > intsec(v, i)
        */
        w = v;
        for(long long e = 18; e >= 0; e--)
        {
            long long temp = cht_anc[w][e];
            if(line_intersect_comp(prev_node[temp], temp, temp, v) == 0)
                w = temp;
        }
        w = cht_anc[w][0];
        cht_anc[v][0] = w;
        for(long long e = 1; e <= 18; e++)
            cht_anc[v][e] = cht_anc[ cht_anc[v][e-1] ][e-1];


        dfs2(v);
    }
}

int main()
{
    long long N;
    cin >> N;

    for(long long j = 1; j <= N-1; j++)
    {
        long long u, v, d;
        cin >> u >> v >> d;

        edge[u].push_back(v);
        dist[u].push_back(d);

        edge[v].push_back(u);
        dist[v].push_back(d);
    }

    for(long long i = 2; i <= N; i++)
        cin >> S[i] >> V[i];

    prev_node[1] = 1;
    prev_dist[1] = 0;
    dfs1(1);


    // for(long long i = 1; i <= N; i++)
    // {
    //     cerr << "i = " << i << ": ";
    //     cerr << S[i] << ' ' << V[i] << ' ' << dist1[i] << " " << prev_node[i] << ' ' << prev_dist[i] << '\n';
    // }

    dp[1] = 0;
    for(long long e = 0; e <= 18; e++)
        cht_anc[1][e] = 1;
    V[1] = S[1] = 0;
    a[1] = b[1] = 0;

    dfs2(1);

    for(long long i = 2; i <= N; i++) cout << dp[i] << ' ';
    cout << '\n';
}

Compilation message (stderr)

harbingers.cpp: In function 'void dfs1(long long int)':
harbingers.cpp:29:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(long long i = 0; i < edge[u].size(); i++)
      |                          ~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100