oj.uz

Submission #257994

# Submission time Handle Problem Language Result Execution time Memory
257994 2020-08-05T07:34:31 Z dolphingarlic Harbingers (CEOI09_harbingers) C++14
100 / 100
 127 ms 20088 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

struct Line {
    ll m, c;
    ll operator()(ll x) { return m * x + c; }
} cht[100001];
int ptr = 0;

double intersect(Line A, Line B) {
    return double(B.c - A.c) / (A.m - B.m);
}

ll dp[100001], s[100001], v[100001], to_root[100001];
vector<pair<int, int>> graph[100001];

void dfs(int node, int parent = 1) {
    int l = 0, r = ptr;
    while (l != r) {
        int mid = (l + r) / 2;
        if (intersect(cht[mid], cht[mid + 1]) >= v[node]) r = mid;
        else l = mid + 1;
    }
    dp[node] = s[node] + v[node] * to_root[node] + cht[l](v[node]);

    Line curr = {-to_root[node], dp[node]};
    l = 0, r = ptr;
    while (l != r) {
        int mid = (l + r) / 2;
        if (intersect(cht[mid], cht[mid + 1]) >= intersect(cht[mid], curr)) r = mid;
        else l = mid + 1;
    }
    int prev_ptr = ptr;
    Line replaced = cht[l + 1];
    cht[l + 1] = curr;
    ptr = l + 1;

    for (pair<int, int> i : graph[node]) if (i.first != parent) {
        to_root[i.first] = to_root[node] + i.second;
        dfs(i.first, node);
    }

    cht[ptr] = replaced;
    ptr = prev_ptr;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, d;
        cin >> u >> v >> d;
        graph[u].push_back({v, d});
        graph[v].push_back({u, d});
    }
    for (int i = 2; i <= n; i++) cin >> s[i] >> v[i];

    for (pair<int, int> i : graph[1]) {
        to_root[i.first] = i.second;
        dfs(i.first);
    }

    for (int i = 2; i <= n; i++) cout << dp[i] << " \n"[i == n];
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 4 ms 3200 KB Output is correct
3 Correct 47 ms 10360 KB Output is correct
4 Correct 84 ms 13944 KB Output is correct
5 Correct 106 ms 17016 KB Output is correct
6 Correct 115 ms 20088 KB Output is correct
7 Correct 62 ms 11768 KB Output is correct
8 Correct 127 ms 16760 KB Output is correct
9 Correct 126 ms 18552 KB Output is correct
10 Correct 114 ms 17396 KB Output is correct