제출 #491462

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
491462		blue	Harbingers (CEOI09_harbingers)	C++17	50 / 100	178 ms	13656 KiB

harbingers

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using pi = pair<int, int>;
using vpi = vector<pi>;

#define sz(x) ((int)x.size())

const int maxN = 100'000;
const int INF = 2'000'000'001;

vi S(1+maxN), V(1+maxN);
vi D(1+maxN, 0);
vi ord(1, 0);

vector<vpi> edge(1+maxN);

void dfs(int u, int p)
{
    ord.push_back(u);
    for(auto k: edge[u])
    {
        if(k.first == p) continue;
        D[k.first] = D[u] + k.second;
        dfs(k.first, u);
    }
}


struct line
{
    ll a;
    ll b;

    ll eval(ll x)
    {
        return a*x + b;
    }
};

bool intersect_comp(line A, line B, line C, line D)
{
    //A.a * x + A.b == B.a * x + B.b, x = (B.b - A.b)/(A.a - B.a)

    ll mul = 1;
    if(A.a - B.a < 0) mul *= -1;
    if(C.a - D.a < 0) mul *= -1;
    return mul * (B.b - A.b) * (C.a - D.a) < mul * (D.b - C.b) * (A.a - B.a);
}

vector<line> cht;

vl dp(1+maxN, INF);

ll query(ll x)
{
    int lo = 0;
    int hi = sz(cht) - 1;
    while(lo != hi)
    {
        int mid = (lo+hi)/2;
        //if(x <= (cht[mid+1].b - cht[mid].b)/(cht[mid].a - cht[mid+1].a))
        ll mul = 1;
        if(cht[mid].a - cht[mid+1].a < 0) mul = -1;
        if(x * (cht[mid].a - cht[mid+1].a) * mul <= (cht[mid+1].b - cht[mid].b) * mul)
            hi = mid;
        else
            lo = mid+1;
    }
    return cht[lo].eval(x);
}

void insert_line(line x)
{
    while(sz(cht) >= 2 && !intersect_comp(cht[sz(cht) - 2], cht[sz(cht) - 1], cht[sz(cht) - 1], x))
        cht.pop_back();

    cht.push_back(x);
}


int main()
{
    int N;
    cin >> N;

    for(int i = 1; i <= N-1; i++)
    {
        int u, v, d;
        cin >> u >> v >> d;
        edge[u].push_back({v, d});
        edge[v].push_back({u, d});
    }

    for(int i = 2; i <= N; i++) cin >> S[i] >> V[i];

    dfs(1, 1);

    insert_line({0, 0});
    dp[1] = 0;

    for(int f = 2; f <= N; f++)
    {
        int i = ord[f];

        dp[i] = ll(S[i]) + ll(V[i])*ll(D[i]) + query(V[i]);
        insert_line({-D[i], dp[i]});
    }

    for(int i = 2; i <= N; i++) cout << dp[i] << ' ';
    cout << '\n';
}

• Subtask 1: 50 / 100