oj.uz

Submission #377297

# Submission time Handle Problem Language Result Execution time Memory
377297 2021-03-13T18:06:24 Z jhwest2 Harbingers (CEOI09_harbingers) C++14
100 / 100
 205 ms 25836 KB 
#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 {
    plint V[MAX];
    int P[20][MAX], pos, sz;

    void update(lint a, lint b) {
        for (int i = 19; i >= 0; i--) {
            if (P[1][P[i][pos]] == 0) continue;
            int c = P[i][pos], p = P[1][c];
            if ((V[c].vb - V[p].vb) / (double)(V[p].va - V[c].va) > (b - V[c].vb) / (double)(V[c].va - a)) pos = p;
        }
        P[1][++sz] = pos; P[0][sz] = sz; pos = sz;
        V[pos] = { a , b };
        for (int i = 2; i < 20; i++) P[i][pos] = P[1][P[i - 1][P[i - 1][pos]]];
    }
    lint query(lint x) {
        int t = pos;
        for (int i = 19; i >= 0; i--) {
            if (P[1][P[i][t]] == 0) continue;
            int c = P[i][t], p = P[1][c];
            if ((V[c].vb - V[p].vb) > (V[p].va - V[c].va) * x) t = p;
        }
        return V[t].va * x + V[t].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 x = C.pos; 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.pos = x;
}
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] << ' ';
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4332 KB Output is correct
2 Correct 7 ms 4844 KB Output is correct
3 Correct 65 ms 13292 KB Output is correct
4 Correct 103 ms 17644 KB Output is correct
5 Correct 115 ms 21740 KB Output is correct
6 Correct 149 ms 25836 KB Output is correct
7 Correct 99 ms 16256 KB Output is correct
8 Correct 205 ms 21864 KB Output is correct
9 Correct 179 ms 23532 KB Output is correct
10 Correct 168 ms 22632 KB Output is correct