oj.uz

Submission #870403

# Submission time Handle Problem Language Result Execution time Memory
870403 2023-11-07T18:12:52 Z paduc Harbingers (CEOI09_harbingers) C++17
100 / 100
 76 ms 24768 KB 
/*
    ▄▄  ▄  ▄ ▄  ▄     ▄▄▄  ▄ ▄ ▄▄▄
   █▄▄█ █▀▄█ █▄▄█    ▄█▄ █ █ █ █
   █  █ █  █ █  █     █▄▄▀ █▄█ █▄▄
*/
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define ull unsigned long long
#define ll long long
#define ld double
#define yes {cout << "YES"; return;}
#define no {cout << "NO"; return;}
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using pii = pair<int,int>;
constexpr int mod = 1e9 + 7;
constexpr ll oo = 1e18;
constexpr ld eps = 1e-9;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int dx[] = {0, 1, 0, -1, -1, 1, 1, -1};
int dy[] = {1, 0, -1, 0, 1, 1, -1, -1};
#define fi first
#define se second
#define name "pad"
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)

template<typename T> bool maximize(T &a, T b) { return a < b && (a = b, true); }
template<typename T> bool minimize(T &a, T b) { return a > b && (a = b, true); }
template<typename T> void compress(vector<T> &v) { sort(all(v)); v.resize(unique(all(v)) - v.begin()); }

struct line{
    int a, b; // y = ax + b
    line(int _a = 0, int _b = 0) { a = _a; b = _b; }
    int f(int x) { return a * x + b; }
    ld intersecX(const line &o) { return (ld) (b - o.b) / (ld) (o.a - a); }
};
bool useless(line cur, line x, line y) {
    return cur.intersecX(x) < x.intersecX(y);
}

struct trace{
    int pos, top;
    line under;
    trace(int _pos = 0, int _top = 0, line _under = line()) {
        pos = _pos; top = _top; under = _under;
    }
};
vector<trace> lst;
int top = 0;

const int N = 1e5 + 5;
vector<pii> adj[N];
int s[N], v[N], n, res[N], d[N];
line lines[N];
int id[N];

bool cmp(int i, int x) {
    return lines[i].intersecX(lines[i + 1]) < x;
}
int get(int x) {
    int i = *lower_bound(id + 1, id + top, x, cmp);
    return lines[i].f(x);
}

void add(line cur) {
    int l = 2, r = top, p = top;
    while(l <= r) {
        int m = (l + r) >> 1;
        if(useless(cur, lines[m], lines[m - 1])) p = m - 1, r = m - 1;
        else l = m + 1;
    }
    ++p;
    lst.push_back({p, top, lines[p]});
    top = p;
    lines[top] = cur;
}

void pop() {
    auto [p, t, u] = lst.back(); lst.pop_back();
    lines[p] = u; top = t;
}

void dfs(int u, int p = -1) {
    if(u > 1) res[u] = get(v[u]) + s[u] + v[u] * d[u];
    add({-d[u], res[u]});
    for(auto &[v, w] : adj[u]) {
        if(v == p) continue;
        d[v] = d[u] + w;
        dfs(v, u);
    }
    pop();
}

int32_t main(){

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
//    freopen(name".inp", "r", stdin);
//    freopen(name".out", "w", stdout);

    cin >> n;
    iota(id + 1, id + n + 1, 1);
    for(int i = 1; i < n; ++i) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for(int i = 2; i <= n; ++i) cin >> s[i] >> v[i];

    dfs(1);
    for(int i = 2; i <= n; ++i) cout << res[i] << ' ';

    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8028 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Correct 30 ms 15564 KB Output is correct
4 Correct 53 ms 18700 KB Output is correct
5 Correct 53 ms 22980 KB Output is correct
6 Correct 68 ms 24768 KB Output is correct
7 Correct 36 ms 16176 KB Output is correct
8 Correct 76 ms 20540 KB Output is correct
9 Correct 76 ms 21608 KB Output is correct
10 Correct 73 ms 20352 KB Output is correct