Submission #1028970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028970		borisAngelov	Harbingers (CEOI09_harbingers)	C++17	70 / 100	1046 ms	32084 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 StackElement
{
    Line rem;
    double from;
    int removedBy;
};

struct ConvexHullTrick
{
    vector<pair<Line, double>> lowerEnvelope;
    stack<StackElement> removedLines;

    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)
    {
        while (lowerEnvelope.size() >= 1 && toRemove(newLine, lowerEnvelope.back()) == true)
        {
            removedLines.push({lowerEnvelope.back().first, lowerEnvelope.back().second, newLine.node});
            lowerEnvelope.pop_back();
        }

        if (lowerEnvelope.empty())
        {
            lowerEnvelope.push_back({newLine, -inf});
        }
        else
        {
            lowerEnvelope.push_back({newLine, cross(newLine, lowerEnvelope.back().first)});
        }
    }

    long long query(long long x)
    {
        if (lowerEnvelope.empty()) return inf;

        int l = 0;
        int r = lowerEnvelope.size() - 1;

        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()
    {
        Line last = lowerEnvelope.back().first;
        lowerEnvelope.pop_back();

        while (!removedLines.empty() && removedLines.top().removedBy == last.node)
        {
            lowerEnvelope.push_back({removedLines.top().rem, removedLines.top().from});
            removedLines.pop();
        }
    }
};

ConvexHullTrick cht;

int a[maxn];
int 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 function 'void dfs(int, int, long long int)':
harbingers.cpp:124: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]
  124 |     for (int i = 0; i < g[node].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~

• Subtask 1: 70 / 100