Submission #377271

#	Time	Username	Problem	Language	Result	Execution time	Memory
377271		jhwest2	Harbingers (CEOI09_harbingers)	C++14	70 / 100	1091 ms	22748 KiB

harbingers

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
typedef pair<lint, lint> plint;
const int MAX = 1e5 + 10;

int n, S[MAX], V[MAX], Dist[MAX];
lint Dp[MAX];
vector<pint> G[MAX];
struct CHT {
    vector<pair<int, lint>> V, Buf;
    void update(int a, lint b) {
        if (V.size() < 2) { V.emplace_back(a, b); return; }
        while (V.size() >= 2) {
            auto p = V[V.size() - 2], c = V.back();
            if ((c.vb - p.vb) * (c.va - a) > (b - c.vb) * (p.va - c.va)) Buf.push_back(V.back()), V.pop_back();
            else break;
        }
        V.emplace_back(a, b);
    }
    lint query(lint x) {
        if (V.size() == 1) return x * V.back().va + V.back().vb;
        int lo = 0, hi = V.size() - 1;
        while (lo < hi) {
            int mid = lo + hi >> 1;
            if ((V[mid + 1].vb - V[mid].vb) < x * (V[mid].va - V[mid + 1].va)) lo = mid + 1;
            else hi = mid;
        }
        return x * V[lo].va + V[lo].vb;
    }
} C;

void dfs(int prv, int cur) {
    if (cur != 1) Dp[cur] = C.query(V[cur]) + (lint)V[cur] * Dist[cur] + S[cur];
    int bs = C.Buf.size();
    C.update(-Dist[cur], Dp[cur]);
    for (auto nxt : G[cur]) {
        if (prv == nxt.vb) continue;
        Dist[nxt.vb] = Dist[cur] + nxt.va;
        dfs(cur, nxt.vb);
    }
    C.V.pop_back();
    while (C.Buf.size() > bs) C.V.push_back(C.Buf.back()), C.Buf.pop_back();
}
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    for (int i = 1; i < n; i++) {
        int x, y, w; cin >> x >> y >> w;
        G[x].emplace_back(w, y); G[y].emplace_back(w, x);
    }
    for (int i = 2; i <= n; i++) cin >> S[i] >> V[i];
    dfs(0, 1);
    for (int i = 2; i <= n; i++) cout << Dp[i] << ' ';
}

Compilation message (stderr)

harbingers.cpp: In member function 'lint CHT::query(lint)':
harbingers.cpp:31:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |             int mid = lo + hi >> 1;
      |                       ~~~^~~~
harbingers.cpp: In function 'void dfs(int, int)':
harbingers.cpp:49:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |     while (C.Buf.size() > bs) C.V.push_back(C.Buf.back()), C.Buf.pop_back();
      |            ~~~~~~~~~~~~~^~~~

• Subtask 1: 70 / 100