Submission #768230

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
768230	2023-06-27T18:56:27 Z	PurpleCrayon	Harbingers (CEOI09_harbingers)	C++17	100 / 100	79 ms	24548 KB

harbingers

#include <bits/stdc++.h>
using namespace std;
 
#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 3e5+10, MOD = 1e9+7;

struct Line {
    ll m, b;

    ll eval(ll x) {
        return m * x + b;
    }
};

int n, x[N], y[N];
ll depth[N], dp[N];
vector<ar<int, 2>> adj[N];

Line hull[N];
int k = 0;

ll qry(ll x) {
    int lo = 0, hi = k, mid = (lo + hi) / 2;
    while (lo < mid && mid < hi) {
        // intersection of hull[mid] and hull[mid-1] <= x
        Line A = hull[mid-1];
        Line B = hull[mid];

        // (B.b - A.b) / (A.m - B.m) <= x
        if ((B.b - A.b) <= (__int128) x * (A.m - B.m)) lo = mid;
        else hi = mid;
        mid = (lo + hi) / 2;
    }
    return hull[lo].eval(x);
}

bool better(Line cur, int i) {
    // true iff intersection point between (i-1, cur) <= (i-1, i)
    Line A = hull[i-1];
    Line B = hull[i];
    // (cur.b - A.b) / (A.m - cur.m) <= (B.b - A.b) / (A.m - B.m)
    return (__int128) (cur.b - A.b) * (A.m - B.m) <= (__int128) (B.b - A.b) * (A.m - cur.m);
}

void dfs(int c, int p) {
    // x[c] + (depth[c] - depth[nxt]) * y[c] + dp[nxt]
    // insert {-depth[nxt], dp[nxt]}
    // query y[c]
    //
    // as you insert, slopes are decreasing

    if (p != -1) {
        dp[c] = qry(y[c]);
        dp[c] += x[c] + depth[c] * y[c];
    }

    int base_k = k;
    pair<int, Line> change{-1, Line{-1, -1}};

    // insert {-depth[nxt], dp[nxt]}
    Line cur = Line{-depth[c], dp[c]};
    if (k >= 2) {
        int lo = 0, hi = k, mid = (lo + hi) / 2;
        while (lo < mid && mid < hi) {
            if (better(cur, mid)) hi = mid;
            else lo = mid;
            mid = (lo + hi) / 2;
        }

        if (hi == k) { // don't delete anything
            change = make_pair(k, hull[k]);
            hull[k++] = cur;
        } else {
            change = make_pair(hi, hull[hi]);
            hull[hi] = cur;
            k = hi+1;
        }
    } else {
        change = make_pair(k, hull[k]);
        hull[k++] = cur;
    }

    for (auto [nxt, w] : adj[c]) if (nxt != p) {
        depth[nxt] = depth[c] + w;
        dfs(nxt, c);
    }

    k = base_k;
    hull[change.first] = change.second;
}

void solve() {
    cin >> n;
    for (int i = 0; i < n-1; i++) {
        int a, b, w; cin >> a >> b >> w, --a, --b;
        adj[a].push_back({b, w}), adj[b].push_back({a, w});
    }
    for (int i = 1; i < n; i++) {
        cin >> x[i] >> y[i];
    }

    dfs(0, -1);
    for (int i = 1; i < n; i++) {
        cout << dp[i] << ' ';
    }
    cout << '\n';
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    // cin >> T;
    while (T--) solve();
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	7380 KB	Output is correct
2	Correct	4 ms	7764 KB	Output is correct
3	Correct	32 ms	14664 KB	Output is correct
4	Correct	47 ms	18252 KB	Output is correct
5	Correct	51 ms	21300 KB	Output is correct
6	Correct	64 ms	24548 KB	Output is correct
7	Correct	40 ms	14832 KB	Output is correct
8	Correct	75 ms	19400 KB	Output is correct
9	Correct	79 ms	21760 KB	Output is correct
10	Correct	76 ms	20540 KB	Output is correct