제출 #1167181

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1167181		spycoderyt	Harbingers (CEOI09_harbingers)	C++20	100 / 100	94 ms	24648 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 3e5 + 5;
struct Line
{
    int a, b;
    int operator()(int x) { return a * x + b; };
} lines[N];
vector<pair<int, int>> A[N];
int dis[N], prep[N], v[N], dp[N];
int sz = 1;

long double inter(Line x, Line y)
{
    return (long double)(x.b - y.b) / (long double)(y.a - x.a);
}
stack<tuple<int, int, Line>> his;
void add(Line nw)
{
    int pos = sz, l = 1, r = sz - 1;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (inter(lines[mid - 1], nw) >= inter(lines[mid], nw))
        {
            pos = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    his.emplace(sz, pos, lines[pos]);
    lines[pos] = nw;
    sz = pos + 1;
}
int query(int x)
{
    int pos = 0, l = 1, r = sz - 1;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if(inter(lines[mid-1],lines[mid]) <= x)
        {
            pos = mid;
            l = mid + 1;
        }
        else
            r = mid - 1;
    }
    return lines[pos](x);
}
void rollback()
{
    auto [a, b, c] = his.top();
    his.pop();
    lines[b] = c;
    sz = a;
}
void dfs(int u, int par = -1)
{
    if (par != -1)
    {
        dp[u] = prep[u] + v[u] * dis[u] + query(v[u]);
        add({-dis[u], dp[u]});
    }
    for (auto [nxt, w] : A[u])
        if (nxt != par)
        {
            dis[nxt] = dis[u] + w;
            dfs(nxt, u);
        }
    if (par != -1)
        rollback();
}
int32_t main()
{

    //   if (fopen("read.inp", "r")){
    //     freopen("read.inp", "r", stdin);
    //     freopen("write.out", "w", stdout);
    //   }
    cin.tie(0)->sync_with_stdio(0);
    int a, b, w, n;
    cin >> n;
    for (int i = 0; i < n - 1; i++)
    {
        cin >> a >> b >> w;
        A[a].push_back({b, w});
        A[b].push_back({a, w});
    }
    for (int i = 2; i <= n; i++)
        cin >> prep[i] >> v[i];
    // get dis values + do lichao
    dfs(1);
    for (int i = 2; i <= n; i++)
        cout << dp[i] << " ";
}

• Subtask 1: 100 / 100