Submission #1029035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029035		borisAngelov	Harbingers (CEOI09_harbingers)	C++17	50 / 100	55 ms	18260 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
const long long inf = (1LL << 62);

int n;
vector<pair<int, int>> g[maxn];

struct Line
{
    long long a;
    long long b;
    int node;

    long long calc(long long x)
    {
        return a * x + b;
    }
};

struct ConvexHullTrick
{
    int sz = 0;
    int ptr = 0;
    pair<Line, double> lowerEnvelope[maxn];
    stack<pair<int, int>> rollback;

    double cross(const Line& l1, const Line& l2)
    {
        return (1.0 * (l1.b - l2.b)) / (1.0 * (l2.a - l1.a));
    }

    bool toRemove(const Line& newLine, pair<Line, double> last)
    {
        if (newLine.a == last.first.a)
        {
            return newLine.b <= last.first.b;
        }

        return cross(newLine, last.first) <= last.second;
    }

    void addLine(Line newLine)
    {
        pair<int, int> roll = {ptr, sz + 1};
        while (ptr >= 1 && toRemove(newLine, lowerEnvelope[ptr]) == true)
        {
            --ptr;
        }

        ++sz;
        lowerEnvelope[sz] = {newLine, -inf};

        if (ptr >= 1)
        {
            lowerEnvelope[sz].second = cross(lowerEnvelope[sz].first, lowerEnvelope[ptr].first);
        }

        ++ptr;
        swap(lowerEnvelope[sz], lowerEnvelope[ptr]);
    }

    long long query(long long x)
    {
        if (ptr == 0) return inf;

        int l = 1;
        int r = ptr;

        while (l <= r)
        {
            int mid = (l + r) / 2;

            if (lowerEnvelope[mid].second <= 1.0 * x)
            {
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }

        return lowerEnvelope[r].first.calc(x);
    }

    void removeLast()
    {
        if (rollback.empty()) return;

        pair<int, int> roll = rollback.top();
        rollback.pop();

        swap(lowerEnvelope[ptr], lowerEnvelope[roll.second]);
        ptr = roll.first;
        --sz;
    }
};

ConvexHullTrick cht;

long long a[maxn];
long long b[maxn];
long long dp[maxn];

void dfs(int node, int par, long long dist)
{
    if (node == 1)
    {
        dp[node] = 0;
    }
    else
    {
        dp[node] = a[node] + b[node] * dist;
        dp[node] = min(dp[node], a[node] + dist * b[node] + cht.query(b[node]));
        cht.addLine({-dist, dp[node], node});
    }

    for (int i = 0; i < g[node].size(); ++i)
    {
        int to = g[node][i].first;
        int w = g[node][i].second;

        if (to != par)
        {
            dfs(to, node, dist + w);
        }
    }

    cht.removeLast();
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n;

    for (int i = 1; i <= n - 1; ++i)
    {
        int x, y, w;
        cin >> x >> y >> w;

        g[x].push_back({y, w});
        g[y].push_back({x, w});
    }

    for (int i = 2; i <= n; ++i)
    {
        cin >> a[i] >> b[i];
    }

    dfs(1, -1, 0);

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

    cout << endl;

    return 0;
}

Compilation message (stderr)

harbingers.cpp: In member function 'void ConvexHullTrick::addLine(Line)':
harbingers.cpp:47:24: warning: variable 'roll' set but not used [-Wunused-but-set-variable]
   47 |         pair<int, int> roll = {ptr, sz + 1};
      |                        ^~~~
harbingers.cpp: In function 'void dfs(int, int, long long int)':
harbingers.cpp:121:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |     for (int i = 0; i < g[node].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~

• Subtask 1: 50 / 100