#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;
const ll MAX = 100007, INF = 1E18 + 9, xL = -1E12 - 7, xR = 1E12 + 7;
ll A[MAX], B[MAX], X[MAX], dp[MAX];
vector<pii> G[MAX];
struct LiChao {
struct Line {
ll a, b;
ll Get(ll x) { return a * x + b; }
};
struct Node {
int L, R;
ll sL, sR;
Line line;
};
vector<Node> tree;
vector<pair<int, Node>> rev;
LiChao() { tree.push_back({ -1, -1, xL, xR, { 0, INF } }); }
void Update(int n, Line v) {
ll sL = tree[n].sL, sR = tree[n].sR, mid = (sL + sR) >> 1;
Line low = tree[n].line, high = v;
if (low.Get(sL) > high.Get(sL)) swap(low, high);
rev.emplace_back(n, tree[n]);
if (low.Get(sR) <= high.Get(sR)) {
tree[n].line = low;
return;
}
if (low.Get(mid) < high.Get(mid)) {
tree[n].line = low;
if (tree[n].R == -1) {
tree[n].R = tree.size();
tree.push_back({ -1, -1, mid + 1, sR, {0, INF} });
}
Update(tree[n].R, high);
}
else {
tree[n].line = high;
if (tree[n].L == -1) {
tree[n].L = tree.size();
tree.push_back({ -1, -1, sL, mid, {0, INF} });
}
Update(tree[n].L, low);
}
}
ll Query(ll n, ll x) {
if (n == -1) return INF;
ll sL = tree[n].sL, sR = tree[n].sR, mid = (sL + sR) >> 1;
return min(tree[n].line.Get(x), (x <= mid ? Query(tree[n].L, x) : Query(tree[n].R, x)));
}
} LT;
void DFS(int cur, int prev, ll d) {
// Insert
ll x = A[cur], cost = B[cur] + A[cur] * d;
dp[cur] = LT.Query(0, x) + cost;
if (cur == 1) dp[cur] = 0;
int tz = LT.tree.size();
LT.Update(0, { -d, dp[cur] });
vector<pair<int, LiChao::Node>> upd = LT.rev;
LT.rev.clear();
for (auto [next, nd] : G[cur]) {
if (next == prev) continue;
DFS(next, cur, d + nd);
}
// Revert
for (auto [n, v] : upd) LT.tree[n] = v;
while (LT.tree.size() > tz) LT.tree.pop_back();
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int N;
cin >> N;
for (int i = 1; i < N; ++i) {
ll a, b, d;
cin >> a >> b >> d;
G[a].emplace_back(b, d);
G[b].emplace_back(a, d);
}
for (int i = 2; i <= N; ++i) cin >> B[i] >> A[i];
DFS(1, 0, 0);
for (int i = 2; i <= N; ++i) cout << dp[i] << ' ';
return 0;
}
Compilation message
harbingers.cpp: In function 'void DFS(int, int, ll)':
harbingers.cpp:68:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
68 | for (auto [next, nd] : G[cur]) {
| ^
harbingers.cpp:74:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
74 | for (auto [n, v] : upd) LT.tree[n] = v;
| ^
harbingers.cpp:75:24: warning: comparison of integer expressions of different signedness: 'std::vector<LiChao::Node>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
75 | while (LT.tree.size() > tz) LT.tree.pop_back();
| ~~~~~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
3980 KB |
Output isn't correct |
| 3 |
Incorrect |
47 ms |
20504 KB |
Output isn't correct |
| 4 |
Incorrect |
79 ms |
30596 KB |
Output isn't correct |
| 5 |
Runtime error |
131 ms |
51104 KB |
Memory limit exceeded |
| 6 |
Runtime error |
163 ms |
50268 KB |
Memory limit exceeded |
| 7 |
Incorrect |
78 ms |
20020 KB |
Output isn't correct |
| 8 |
Incorrect |
144 ms |
29036 KB |
Output isn't correct |
| 9 |
Runtime error |
143 ms |
52948 KB |
Memory limit exceeded |
| 10 |
Runtime error |
96 ms |
65536 KB |
Execution killed with signal 9 |
