Submission #953397

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
953397	2024-03-26T00:10:40 Z	GasmaskChan	Harbingers (CEOI09_harbingers)	C++17	100 / 100	84 ms	24512 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6744 KB	Output is correct
2	Correct	3 ms	7004 KB	Output is correct
3	Correct	39 ms	14416 KB	Output is correct
4	Correct	61 ms	17344 KB	Output is correct
5	Correct	58 ms	22392 KB	Output is correct
6	Correct	78 ms	24512 KB	Output is correct
7	Correct	51 ms	15300 KB	Output is correct
8	Correct	84 ms	19572 KB	Output is correct
9	Correct	82 ms	20852 KB	Output is correct
10	Correct	70 ms	19520 KB	Output is correct