제출 #1211730

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1211730		chikien2009	Harbingers (CEOI09_harbingers)	C++20	0 / 100	131 ms	96136 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
{
    long long 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 NODE
{
    LINE v;
    int l, r;
};

struct LICHAOTREE
{
    int sz = 0;
    NODE tree[3200000];

    inline int Update(int ind, int l, int r, LINE inp)
    {
        int new_ind = sz++;
        if (ind == -1)
        {
            tree[new_ind].v = inp;
            tree[new_ind].l = tree[new_ind].r = -1;
        }
        else
        {
            tree[new_ind] = tree[ind];
            int m = (l + r) >> 1;
            if (tree[new_ind].v.Val(m) > inp.Val(m))
            {
                swap(tree[new_ind].v, inp);
            }
            if (l < r)
            {
                if (tree[new_ind].v.Val(l) > inp.Val(l))
                {
                    tree[new_ind].l = Update(tree[ind].l, l, m, inp);
                }
                if (tree[new_ind].v.Val(r) > inp.Val(r))
                {
                    tree[new_ind].r = Update(tree[ind].r, m + 1, r, inp);
                }
            }
        }
        return new_ind;
    }
    inline long long Get(int ind, int l, int r, int x)
    {
        if (ind == -1)
        {
            return 9e18;
        }
        if (l == r)
        {
            return tree[ind].v.Val(x);
        }
        int m = (l + r) >> 1;
        if (x <= m)
        {
            return min(tree[ind].v.Val(x), Get(tree[ind].l, l, m, x));
        }
        return min(tree[ind].v.Val(x), Get(tree[ind].r, m + 1, r, x));
    }
} lct;

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)
{
    if (node == 0)
    {
        id[node] = lct.Update(-1, 1, 1e9, LINE(0, 0));
    }
    else
    {
        f[node] = (long long)v[node] * road + s[node] + lct.Get(id[par], 1, 1e9, v[node]);
        id[node] = lct.Update(id[par], 1, 1e9, LINE(-road, f[node]));
    }
    for (auto & i : g[node])
    {
        if (i.first != par)
        {
            DFS(i.first, node, road + i.second);
        }
    }
}

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: 0 / 100