Submission #1123387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123387		HiepVu217	Harbingers (CEOI09_harbingers)	C++20	100 / 100	84 ms	19016 KiB

harbingers

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 17;
int n, sz, z;
vector <pair <int, int>> adj[N];
long long s[N], v[N], d[N], f[N];
struct line
{
    long long a, b;
} cv[N];
bool bad (line x, line y, line z)
{
    return 1.0 * (x.b - z.b) / (z.a - x.a) < 1.0 * (x.b - y.b) / (y.a - x.a);
}
long long calc (int x)
{
    int l = 1, r = sz;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (cv[mid].a * x + cv[mid].b < cv[mid + 1].a * x + cv[mid + 1].b)
        {
            r = mid;
            continue;
        }
        l = mid + 1;
    }
    return cv[l].a * x + cv[l].b;
}
int findz (line x)
{
    if (!bad (cv[sz - 1], cv[sz], x) || !sz)
    {
        return sz + 1;
    }
    int l = 2, r = sz;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (bad (cv[mid - 1], cv[mid], x))
        {
            r = mid;
            continue;
        }
        l = mid + 1;
    }
    return l;
}
void dfs (int u, int pr)
{
    f[u] = calc (v[u]) + d[u] * v[u] + s[u];
    int _sz = sz;
    sz = findz ({-d[u], f[u]});
    line pre = cv[sz];
    cv[sz] = {-d[u], f[u]};
    for (auto [_u, w]: adj[u])
    {
        if (_u == pr)
        {
            continue;
        }
        d[_u] = d[u] + w;
        dfs (_u, u);
    }
    cv[sz] = pre;
    sz = _sz;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 2, u, v, w; i <= n; ++i)
    {
        cin >> u >> v >> w;
        adj[u].push_back ({v, w});
        adj[v].push_back ({u, w});
    }
    for (int i = 2; i <= n; ++i)
    {
        cin >> s[i] >> v[i];
    }
    dfs (1, 1);
    for (int i = 2; i <= n; ++i)
    {
        cout << f[i] << " ";
    }
}

• Subtask 1: 100 / 100