제출 #1278394

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278394		Ice_man	Harbingers (CEOI09_harbingers)	C++20	0 / 100	133 ms	28872 KiB

harbingers

/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include <iostream>
#include <chrono>

#include <vector>


#define maxn 200005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define PB push_back
#define X first
#define Y second
#define control cout<<"passed"<<endl;


typedef unsigned long long ull;
typedef long long ll;
typedef __int128 lint;

typedef std::pair <ll, ll> pll;
typedef std::pair <ll, ll> pil;
typedef std::pair <ll, ll> pli;
typedef long double ld;

struct CHT
{
    std::vector <pll> hull;

    lint calc(pll curr, ll x)
    {
        return (lint)(curr.X) * x + curr.Y;
    }

    long double llersection(pll a, pll b)
    {
        return (lint)(b.Y - a.Y) / (a.X - b.X);
    }

    bool check(pll l1 , pll l2 , pll l3)
    {
        return __int128(l2.Y - l1.Y) * (l2.X - l3.X) >= __int128(l3.Y - l2.Y) * (l1.X - l2.X);
    }

    void add_line(pll curr)
    {
        while(hull.size() >= 2)
        {
            if(check(hull[hull.size() - 2] , hull.back() , curr) == true)
                hull.pop_back();
            else
                break;
        }
        hull.PB(curr);
    }

    ll query(double x)
    {
        if(hull.size() == 0)
            return 4e18;

        ll l = 0, r = hull.size() - 1;

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

            if(calc(hull[mid], x) > calc(hull[mid + 1], x))
                l = mid + 1;
            else
                r = mid;
        }

        return calc(hull[l], x);
    }
};



std::vector <pll> v[maxn];
ll depth[maxn], sz[maxn], up[maxn], lead[maxn];
std::vector <ll> d[maxn];
ll dist[maxn];

void dfs_sz(ll node, ll par)
{
    d[depth[node]].PB(node);
    up[node] = par;
    sz[node] = 1;
    for(auto& nb : v[node])
    {
        if(nb.X == par)
            continue;

        depth[nb.X] = depth[node] + 1;
        dist[nb.X] = dist[node] + nb.Y;
        dfs_sz(nb.X, node);
        sz[node] += sz[nb.X];
    }
}

ll heavy[maxn];

ll cnt = 0;

void dfs_hld(ll node, ll par, ll le)
{
    //std::cout << node << " " << par << " " << le << "\n";

    lead[node] = le;

    heavy[node] = -1;
    for(auto& nb : v[node])
    {
        if(nb.X == par)
            continue;
        if(heavy[node] == -1 || (sz[nb.X] > sz[heavy[node]] && nb.X != par))
            heavy[node] = nb.X;
    }


    //std::cout << "!! " << heavy[node] << "\n";

    if(heavy[node] == -1)
        return;

    dfs_hld(heavy[node], node, le);

    for(auto& nb : v[node])
        if(nb.X != par && nb.X != heavy[node])
            dfs_hld(nb.X, node, nb.X);
}

CHT h[maxn];

ll speed[maxn], wait[maxn];

ll answer(ll node)
{
    //std::cout << "------------------------------" << "\n";
    //std::cout << node << "\n";
    ll ans = 4e18;
    ll start = node;

    while(node != 0)
    {
        /**std::cout << node << "\n";
        std::cout << h[lead[node]].query(speed[start]) << "\n";

        std::cout << "!!!!!" << "\n" << speed[node] << ": ";
        for(auto& e : h[lead[node]].hull)
            std::cout << "{ " << e.X << " " << e.Y << " } ";
        std::cout << "\n";
        std::cout << "!!!!!" << "\n";*/
        ans = std::min(ans, h[lead[node]].query(-speed[start]));
        node = up[lead[node]];
    }

    return ans;
}

ll n;
ll dp[maxn];

void read()
{
    std::cin >> n;

    for(ll i = 1; i <= n - 1; i++)
    {
        ll x, y, z;
        std::cin >> x >> y >> z;

        v[x].PB({y, z});
        v[y].PB({x, z});
    }

    for(ll i = 1; i <= n - 1; i++)
        std::cin >> wait[i + 1] >> speed[i + 1];

    dist[1] = 0;
    up[1] = 0;
    depth[1] = 0;
    dfs_sz(1, 0);

    //std::cout << "here" << "\n";


    dfs_hld(1, 0, 1);

    //std::cout << "here" << "\n";

    dp[1] = 0;
    for(ll i = 1; i <= n - 1; i++)
    {
        //std::cout << "****************************" << "\n";

        for(auto& node : d[i])
        {
            dp[node] = wait[node] + speed[node] * dist[node];
            //std::cout << "?------? " << node << " " << answer(node)  << " " <<  dist[node] * speed[node] + wait[node] << "\n";
            ll pom = answer(node);
            if(pom == 4e18)
                continue;
            dp[node] = std::min(dp[node], pom + dist[node] * speed[node] + wait[node]);
        }

        for(auto& node : d[i])
            h[lead[node]].add_line({dist[node], dp[node]});
    }


    for(ll i = 2; i <= n; i++)
        std::cout << dp[i] << " ";
    std::cout << "\n";
}













int main()
{

    /**#ifdef ONLINE_JUDGE /// promeni
        freopen("taxi.in", "r", stdin);
        freopen("taxi.out", "w", stdout);
    #endif*/

    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);


    read();


    return 0;
}

• Subtask 1: 0 / 100