oj.uz

Submission #796610

# Submission time Handle Problem Language Result Execution time Memory
796610 2023-07-28T14:46:34 Z hungby04 Harbingers (CEOI09_harbingers) C++17
100 / 100
 93 ms 19864 KB 
/// HuDzG
#include <bits/stdc++.h>
#define reset(a) memset(a,0,sizeof(a))
#define ll long long
#define ld long double
#define endl '\n'
#define AutoAC int main()
#define OO 9000000000000000000
#define F first
#define S second
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pb push_back
#define mp make_pair
#define nmax 100005
#define HUNGIT "C"
#define MOD 1000000007

using namespace std;
// https://oj.vnoi.info/problem/harbinge
int n;
vector <pii> adj[nmax];
ll h[nmax];
int s[nmax], v[nmax];
ll f[nmax];
vector <int> node;

struct Line
{
    ll a, b;
    Line(ll a = 0, ll b = 0) : a(a), b(b) {}

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

double slope(Line A, Line B)
{
    return (double) (A.b - B.b) / (B.a - A.a);
}

Line Stack[nmax];
int stackSize = 0;

ll Get(ll x)
{
    if(stackSize == 1) 
    {
        return Stack[1].getValue(x);
    }
    int l = 1, r = stackSize - 1, res = stackSize;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(slope(Stack[mid], Stack[mid + 1]) >= x)
        {
            res = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return Stack[res].getValue(x);
}

int findPos(Line tmp)
{
    if(stackSize == 1) return 1;
    int l = 1, r = stackSize - 1, res = stackSize;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(slope(Stack[mid], Stack[mid + 1]) >= slope(tmp, Stack[mid + 1]))
        {
            res = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return res;
}

void dfs(int u, int p)
{
    if(u > 1)
    {
        // f[u] = OO;
        // for(int x : node)
        //     f[u] = min(f[u], s[u] + v[u] * (h[u] - h[x]) + f[x]);
        f[u] = Get(v[u]) + s[u] + 1ll * v[u] * h[u];
    }
    Line tmp(-h[u], f[u]);
    int pos = findPos(tmp) + 1;
    int saveSize = stackSize;
    Line saveLine = Stack[pos];
    Stack[pos] = tmp;
    stackSize = pos;
    for(pii v : adj[u])
        if(v.F != p)
        {
            h[v.F] = h[u] + v.S;
            dfs(v.F, u);
        }
    Stack[pos] = saveLine;
    stackSize = saveSize;
}

void solve()
{
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].pb(mp(v, w));
        adj[v].pb(mp(u, w));
    }
    for(int i = 2; i <= n; i++)
        cin >> s[i] >> v[i];
    dfs(1, 0);
    for(int i = 2; i <= n; i++)
        cout << f[i] << " ";
}

AutoAC
{
    // clock_t START, FINISH;
    // START = clock();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen (HUNGIT".inp", "r", stdin);
    // freopen (HUNGIT".out", "w", stdout);
    int T = 1;

    // cin >> T;

    for (int i = 1; i <= T; i++)
    {
        solve();
    }

    // FINISH = clock();
    // cout << fixed << setprecision(4);
    // cout << endl << "TIME: " << (ld)((ld)(FINISH - START) / CLOCKS_PER_SEC);
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 3 ms 4564 KB Output is correct
3 Correct 27 ms 10784 KB Output is correct
4 Correct 39 ms 13824 KB Output is correct
5 Correct 45 ms 16844 KB Output is correct
6 Correct 58 ms 19864 KB Output is correct
7 Correct 36 ms 11220 KB Output is correct
8 Correct 93 ms 14868 KB Output is correct
9 Correct 92 ms 16776 KB Output is correct
10 Correct 67 ms 15780 KB Output is correct