Submission #965411

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
965411	2024-04-18T13:03:53 Z	MisterReaper	Harbingers (CEOI09_harbingers)	C++17	100 / 100	90 ms	19900 KB

harbingers

#include <bits/stdc++.h>
using i64 = long long;

constexpr int maxN = 1E5 + 5;
constexpr i64 INF = 1E18;
constexpr __int128 ONE = 1;

int N;
std::vector<std::pair<int, int>> adj[maxN];
int S[maxN], V[maxN], par[maxN], D[maxN];
i64 dp[maxN];

struct line {
    i64 a, b;
    line() : a(0), b(0) {}
    line(i64 _a, i64 _b) : a(_a), b(_b) {}
    i64 eval(i64 x) {
        return 1LL * a * x + b;
    }
    long double intersect(line rhs) {
        return (long double)(rhs.b - b) / (a - rhs.a);
    }
};

int sz;
line dq[maxN];
int size() { return sz; }

i64 query(i64 x) {
    int l = 0, r = size() - 1;
    while(r - l > 3) {
        int m = (l + r) >> 1;
        if(dq[m].intersect(dq[m + 1]) <= x) {
            l = m;
        } else {
            r = m;
        }
    }

    i64 res = INF;
    for(int i = l; i <= r; i++) {
        res = std::min(res, dq[i].eval(x));
    }
    return res;
}

int removep(line L) {
    if(size() < 2 || L.intersect(dq[size() - 1]) >= dq[size() - 1].intersect(dq[size() - 2])) {
        return size();
    }
    int l = 1, r = size() - 1;
    while(l < r) {
        int m = (l + r) >> 1;
        if(L.intersect(dq[m]) < dq[m].intersect(dq[m - 1])) {
            r = m;
        } else {
            l = m + 1;
        }
    }
    return l;
}

void dfs(int v) {
    int pmax, ppos;
    line pline;
    if(v != 1) {
        dp[v] = query(V[v]) + 1LL * D[v] * V[v] + S[v];
        line l = {-D[v], dp[v]};
        pmax = sz;
        ppos = sz = removep(l);
        pline = dq[ppos];
        dq[sz++] = l;
    } else {
        dq[sz++] = {0, 0};
    }
    for(auto [u, w] : adj[v]) {
        if(u == par[v]) {
            continue;
        }
        D[u] = D[v] + w;
        par[u] = v;
        dfs(u);
    }

    if(v != 1) {
        sz = pmax;
        dq[ppos] = pline;
    }
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> N;
    for(int i = 1; i <= N - 1; i++) {
        int A, B, W;
        std::cin >> A >> B >> W;
        adj[A].emplace_back(B, W);
        adj[B].emplace_back(A, W);
    }

    for(int i = 2; i <= N; i++) {
        std::cin >> S[i] >> V[i];
    }

    std::fill_n(&dp[1], N, INF);
    dp[1] = 0;
    par[1] = 1;
    dfs(1);

    for(int i = 2; i <= N; i++) {
        std::cout << dp[i] << " \n"[i == N];
    }

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	6492 KB	Output is correct
2	Correct	3 ms	7004 KB	Output is correct
3	Correct	32 ms	12380 KB	Output is correct
4	Correct	46 ms	14932 KB	Output is correct
5	Correct	47 ms	17488 KB	Output is correct
6	Correct	60 ms	19900 KB	Output is correct
7	Correct	38 ms	12112 KB	Output is correct
8	Correct	90 ms	15092 KB	Output is correct
9	Correct	77 ms	16848 KB	Output is correct
10	Correct	74 ms	15824 KB	Output is correct