Submission #1211754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211754		chikien2009	Harbingers (CEOI09_harbingers)	C++20	40 / 100	153 ms	32836 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;

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

struct LINE
{
    double a, b;
    inline LINE()
    {
        a = 1e9;
        b = 1e18;
    }
    inline LINE(long long new_a, long long new_b)
    {
        a = new_a;
        b = new_b;
    }
    inline long long Val(long long x)
    {
        return a * x + b;
    }
};

struct CONVEX_HULL
{
    vector<LINE> v;

    inline bool Check(LINE x, LINE y, LINE z)
    {
        double i1 = (x.b - y.b) / (y.a - x.a);
        double i2 = (x.b - z.b) / (z.a - x.a);
        return i1 > i2;
    }
    inline vector<LINE> Add(LINE inp)
    {
        vector<LINE> removed;
        while (v.size() > 1 && Check(v[v.size() - 2], v[v.size() - 1], inp))
        {
            removed.push_back(v.back());
            v.pop_back();
        }
        v.push_back(inp);
        return removed;
    }
    inline void Revive(vector<LINE> inp)
    {
        v.pop_back();
        for (auto & i : inp)
        {
            v.push_back(i);
        }
    }
    inline long long Get(long long x)
    {
        int l = 0, r = v.size() - 1, m;
        long long res = 9e18;
        while (l <= r)
        {
            m = (l + r) >> 1;
            res = min(res, v[m].Val(x));
            if (m + 1 < v.size() && v[m].Val(x) > v[m + 1].Val(x))
            {
                l = m + 1;
            }
            else
            {
                r = m - 1;
            }
        }
        return res;
    }
} cht;

int id[100000], n, a, b, c, s[100000], v[100000];
long long f[100000];
vector<pair<int, int>> g[100000];

inline void DFS(int node, int par, int road)
{
    vector<LINE> keep;
    if (node == 0)
    {
        keep = cht.Add(LINE(0, 0));
    }
    else
    {
        f[node] = cht.Get(v[node]) + (long long)road * v[node] + s[node];
        keep = cht.Add(LINE(-road, f[node]));
    }
    for (auto & i : g[node])
    {
        if (i.first != par)
        {
            DFS(i.first, node, road + i.second);
        }
    }
    cht.Revive(keep);
}

int main()
{
    setup();

    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> a >> b >> c;
        g[a - 1].push_back({b - 1, c});
        g[b - 1].push_back({a - 1, c});
    }
    for (int i = 1; i < n; ++i)
    {
        cin >> s[i] >> v[i];
    }
    DFS(0, 0, 0);
    for (int i = 1; i < n; ++i)
    {
        cout << f[i] << " ";
    }
    return 0;
}

• Subtask 1: 40 / 100