Submission #953397

#	Time	Username	Problem	Language	Result	Execution time	Memory
953397		GasmaskChan	Harbingers (CEOI09_harbingers)	C++17	100 / 100	84 ms	24512 KiB

harbingers

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define MAX 100005


int h[MAX];
vector<pair<int, int>> g[MAX];

void dfs(int u, int p)
{
    for (auto &[v, w] : g[u])
        if (v != p)
            h[v] = h[u] + w, dfs(v, u);
}

double insect(pair<int, int> a, pair<int, int> b)
{
    return (1.0 * b.second - a.second) / (1.0 * a.first - b.first);
}

int cntlines;
pair<int, int> lines[MAX];
vector<pair<pair<int, int>, pair<int, int>>> deleted;

void addline(pair<int, int> line)
{
    int mid, l = 1, r = cntlines - 1, posi = cntlines;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        if (insect(lines[mid], line) >= insect(lines[mid - 1], line))
        {
            posi = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }

    deleted.push_back({{posi, cntlines}, lines[posi]});
    cntlines = posi + 1;
    lines[posi] = line;
}

int getval(int x, pair<int, int> line)
{
    return x * line.first + line.second;
}

int getline(int x)
{
    int mid, l = 1, r = cntlines - 1, posi = 0;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        if (insect(lines[mid], lines[mid - 1]) >= (double)x)
        {
            posi = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return getval(x, lines[posi]);
}

int s[MAX], vel[MAX], f[MAX];

void dp(int u, int p)
{
    if (u != 1) f[u] = getline(-vel[u]) + s[u] + h[u] * vel[u];
    addline({h[u], f[u]});
    for (auto &[v, w] : g[u])
        if (v != p)
            dp(v, u);
    auto cur = deleted.back();
    deleted.pop_back();
    cntlines = cur.first.second;
    lines[cur.first.first] = cur.second;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout);
    int n;
    cin >> n;
    for (int u, v, w, i = 1; i < n; i++)
    {
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }

    for (int i = 2; i <= n; i++) cin >> s[i] >> vel[i];

    dfs(1, 0);
    dp(1, 0);
    for (int i = 2; i <= n; i++) cout << f[i] << ' ';
    return 0;
}

• Subtask 1: 100 / 100