Submission #425117

#	Time	Username	Problem	Language	Result	Execution time	Memory
425117		blue	Harbingers (CEOI09_harbingers)	C++17	0 / 100	300 ms	22432 KiB

harbingers

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

vector<int> edge[100001], wt[100001];
vector<int> order(2, 1), order_index(100001), prev_weight(100001, 0);
vector<int> visit(100001, 0);
vector<long long> S(100001), V(100001);

void dfs(int u)
{
    // cerr << "dfs" << u << '\n';
    visit[u] = 1;
    for(int e = 0; e < edge[u].size(); e++)
    {
        int v = edge[u][e], w = wt[u][e];
        if(visit[v]) continue;

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

        order_index[v] = order.size();
        order.push_back(v);
        // cerr << "pv " << order_index[v] << " = " << w << '\n';
        prev_weight[ order_index[v] ] = w;

        dfs(v);
    }
}

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

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

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

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

    order_index[1] = 1;
    dfs(1);

    // for(int x: order) cerr << x << ' ';
    // cerr << '\n';
    // for(int k = 0; k <= N+5; k++) cerr << order_index[k] << ' ';
    // cerr << '\n';

    for(int i = 2; i <= N; i++)
    {
        int s, v;
        cin >> s >> v;

        S[ order_index[i] ] = s;
        V[ order_index[i] ] = v;
    }

    long long dist1[N+1];
    dist1[1] = 0;

    for(int i = 2; i <= N; i++)
        dist1[i] = dist1[i-1] + prev_weight[i];

    // for(int i = 1; i <= N; i++) cerr << dist1[i] << ' ';
    // cerr << '\n';

    // for(int i = 1; i <= N; i++) cerr << S[i] << ' ' << V[i] << '\n';

    vector<long long> dp(N+1, 0);

    /*
    p[u] = min{S[u] + V[u]*(dist1[u] - dist1[v]) + dp[v] | v =1..u-1}
          = S[u] + V[u]*dist1[u] + min{-dist1[v]*V[u] + dp[v] | v=1..u-1}

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


    deque<int> lines;
    lines.push_back(1);

    for(int i = 2; i <= N; i++)
    {
        while(lines.size() >= 2)
        {
            long long a1 = -dist1[lines[0]];
            long long b1 = dp[lines[0]];

            long long a2 = -dist1[lines[1]];
            long long b2 = dp[lines[1]];

            if(a2 < a1)
            {
                swap(a1, a2);
                swap(b1, b2);
            }

            // if(V[u] >= (b1-b2)/(a2-a1))
            if(V[i]*(a2-a1) >= b1-b2)
            {
                // cerr << "popping " << lines.front() << " from front \n";
                lines.pop_front();
            }
            else break;
        }

        int j = lines[0];
        // cerr << "j = " << j << '\n';
        dp[i] = S[i] + V[i]*(dist1[i] - dist1[j]) + dp[j];


        while(lines.size() >= 2)
        {
            long long a1 = -dist1[lines[ lines.size()-2 ]];
            long long b1 = dp[lines[ lines.size()-2 ]];

            long long a2 = -dist1[lines[ lines.size()-1 ]];
            long long b2 = dp[lines[ lines.size()-1 ]];

            long long a_curr = -dist1[i];
            long long b_curr = dp[i];

            /*
                if((b1-b2)/(a2-a1) >= (b1-b_curr)/(a_curr-a2))
            */

            // if(intersect(-2, -1) >= intersect(-1, curr))
            if((b1-b2)*(a_curr-a2) >= (b1-b_curr)*(a2-a1))
            {
                // cerr << "popping " << lines.back() << " from back\n";
                lines.pop_back();
            }
            else break;
        }
        // cerr << "pushing " << i << " to back\n";
        lines.push_back(i);
    }

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

Compilation message (stderr)

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

• Subtask 1: 0 / 100