Submission #425046

#	Time	Username	Problem	Language	Result	Execution time	Memory
425046		blue	Harbingers (CEOI09_harbingers)	C++17	0 / 100	470 ms	39312 KiB

harbingers

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

const long long INF = 1'000'000'000'000'000'000LL;
const int maxN = 100000;
int N;
vector<int> edge[maxN+1];
vector<long long> wt[maxN+1];
long long S[maxN+1], V[maxN+1];

vector<int> parent(maxN+1, -1);
vector<long long> dist1(maxN+1);
vector< vector<int> > cht_anc(maxN+1, vector<int>(20));

vector<long long> dp(maxN+1, INF);


/*
dp[u] = min{S[u] + V[u]*(dist1[u] - dist1[v]) + dp[v] | v in ancs[u]}
      = S[u] + V[u]*dist1[u] + min{-dist1[v]*V[u] + dp[v] | v in ancs[u]}

line = ax + b = -dist1[v] * V[u]  +  dp[v]
*/



bool cmp_Xgeq(long long X, int l1, int l2) // return X >= intersect(l1, l2)
{
    if(l1 == 0 || l2 == 0) return 1;

    long long a1 = -dist1[l1];
    long long b1 = dp[l1];

    long long a2 = -dist1[l2];
    long long b2 = dp[l2];

    //guarantee a1 >= a2
    if(a1 < a2)
    {
        swap(a1, a2);
        swap(b1, b2);
    }

    /*intersect((a1, b1), (a2, b2)) = I
        a1*I + b1 = a2*I + b2
        (a1-a2)I = b2-b1
        I = (b2-b1)/(a1-a2)
    */

    return (   (a1-a2)*X >= b2-b1   );
}



bool cmp_lines(int l1, int l2, int L1, int L2)
{
    if(l1 == 0 || l2 == 0) return 0;
    if(L1 == 0 || L2 == 0) return 1;


    long long a1 = -dist1[l1];
    long long b1 = dp[l1];

    long long a2 = -dist1[l2];
    long long b2 = dp[l2];

    //guarantee a1 >= a2
    if(a1 < a2)
    {
        swap(a1, a2);
        swap(b1, b2);
    }



    long long A1 = -dist1[L1];
    long long B1 = dp[L1];

    long long A2 = -dist1[L2];
    long long B2 = dp[L2];

    //guarantee A1 >= A2
    if(A1 < A2)
    {
        swap(A1, A2);
        swap(B1, B2);
    }

    //return (b2-b1)/(a1-a2) <= (B2-B1)/(A1-A2)
    return (b2-b1)*(A1-A2) < (B2-B1)*(a1-a2);
}





void dfs(int u)
{
    // cerr << "\n\n\n\n\n\n\n\n";
    // cerr << "!!! DFS " << u << " !!! \n";

    if(u != 1)
    {

        /*
        PART 1: Locate the optimal line to compute dp[u] from.
        We locate a CHT ancestor of u: v which is the optimal line.

        We want the highest possible v such that V[u] >= intersect(v, p[v])
        */

        int v = parent[u];

        // cerr << v << ' ' << cht_anc[v][0] << ' ' << cht_anc[v][1] << '\n';

        // for(int bit = 19; bit >= 0; bit--)
        // {
        //     if(cht_anc[v][bit] == 0) continue;
        //     // cerr << "bit = " << bit << '\n';
        //
        //     int temp = cht_anc[v][bit];
        //
        //     // cerr << "temp = " << temp << '\n';
        //
        //     if(cmp_Xgeq(V[u], temp, cht_anc[temp][0]))
        //     {
        //         v = temp;
        //         // cerr << "jumped! \n";
        //     }
        // }

        int v1 = parent[u];
        for(int bit = 19; bit >= 0; bit--)
        {
            // if(cht_anc[v1][bit] == 0) continue;
            int temp = cht_anc[v1][bit];
            if(temp == 0 || cht_anc[temp][0] == 0) continue;

            if(!cmp_Xgeq(V[u], temp, cht_anc[temp][0]))
            {
                v1 = temp;
            }
        }

        if(!cmp_Xgeq(V[u], v1, cht_anc[v1][0]))
            v = parent[v1];
        else
            v = v1;

        // cerr << "computation v = " << v << '\n';

        dp[u] = S[u] + V[u]*(dist1[u] - dist1[v]) + dp[v];



        // cerr << "ideal evaluator line for " << u << " = " << v << '\n';
        // cerr << "for line " << u << ", a = " << -dist1[u] << " and b = " << dp[u] << '\n';
        //
        // cerr << "\n\n";




        /*
        PART 2: Find the appropriate CHT parent of u.

        Find the first ancestor a such that intersect(p[a], a) < intersect(a, u)

        Find the last ancestor v such that intersect(p[v], v) >= intersect(v, u);
        */


        cht_anc[u][0] = parent[u];

        v = u;

        for(int bit = 19; bit >= 0; bit--)
        {
            int temp = cht_anc[v][bit];
            if(temp == 0 || cht_anc[temp][0] == 0) continue;

            if(cmp_lines(temp, u,  temp, cht_anc[temp][0]))
            {
                v = temp;
            }
            // cerr << "bit = " << bit << ", v = " << temp << '\n';
        }

        int a = cht_anc[v][0];

        // cerr << "cht parent of " << u << " = " << a << '\n';

        cht_anc[u][0] = a;
        for(int bit = 1; bit < 20; bit++)
            cht_anc[u][bit] = cht_anc[  cht_anc[u][bit-1]  ][bit-1];

    }










    for(int e = 0; e < edge[u].size(); e++)
    {
        int v = edge[u][e];
        long long d = wt[u][e];

        if(parent[v] != -1) continue;

        parent[v] = u;
        dist1[v] = dist1[u] + d;

        dfs(v);
    }
}

int main()
{
    cin >> N;

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

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

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

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

    parent[1] = 0;
    dist1[1] = 0;
    dp[1] = 0;
    S[1] = V[1] = 0;
    for(int x = 0; x < 20; x++)
        cht_anc[1][x] = 0;

    // cerr << "check\n";

    dfs(1);

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

Compilation message (stderr)

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

• Subtask 1: 0 / 100