Submission #796610

#	Time	Username	Problem	Language	Result	Execution time	Memory
796610		hungby04	Harbingers (CEOI09_harbingers)	C++17	100 / 100	93 ms	19864 KiB

harbingers

/// 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 / 100