#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e5 + 10;
const int M = 20 * N;
const int inf = 1e9;
int n, s[N], t[N];
ll dp[N], dep[N];
vector<pair<int, int>> g[N];
struct Line {
ll k, n;
Line() { k = 0; n = 1e18; }
Line(ll _k, ll _n) : k(_k), n(_n) {}
ll eval(ll x) { return k * x + n; }
} st[M];
int root[N], ls[M], rs[M], tsz;
void modify(int& v, int pv, int l, int r, Line ln) {
v = ++tsz;
ls[v] = ls[pv];
rs[v] = rs[pv];
st[v] = st[pv];
int mid = l + r >> 1;
if (ln.eval(mid) < st[v].eval(mid)) {
swap(st[v], ln);
}
if (l == r) return;
if (ln.eval(l) < st[v].eval(l)) {
modify(ls[v], ls[pv], l, mid, ln);
} else {
modify(rs[v], rs[pv], mid + 1, r, ln);
}
}
ll query(int v, int l, int r, int p) {
if (l == r) {
return st[v].eval(p);
}
int mid = l + r >> 1;
ll res = st[v].eval(p);
if (p <= mid) {
res = min(res, query(ls[v], l, mid, p));
} else {
res = min(res, query(rs[v], mid + 1, r, p));
}
return res;
}
void dfs(int v, int pv) {
// (dep[x] - dep[y]) * speed[x] + dp[y] + time[x]
if (v != 1) {
dp[v] = query(root[pv], 1, inf, s[v]) + dep[v] * s[v] + t[v];
}
modify(root[v], root[pv], 1, inf, Line(-dep[v], dp[v]));
for (auto& e : g[v]) {
int u = e.first;
int w = e.second;
if (u == pv) {
continue;
}
dep[u] = dep[v] + w;
dfs(u, v);
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
for (int i = 2; i <= n; i++) {
scanf("%d%d", &t[i], &s[i]);
}
dfs(1, 1);
for (int i = 2; i <= n; i++) {
printf("%lld ", dp[i]);
}
return 0;
}
Compilation message
harbingers.cpp: In function 'void modify(int&, int, int, int, Line)':
harbingers.cpp:22:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
22 | int mid = l + r >> 1;
| ~~^~~
harbingers.cpp: In function 'long long int query(int, int, int, int)':
harbingers.cpp:37:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
37 | int mid = l + r >> 1;
| ~~^~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:63:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
harbingers.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
66 | scanf("%d%d%d", &u, &v, &w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | scanf("%d%d", &t[i], &s[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
33984 KB |
Memory limit exceeded |
| 2 |
Runtime error |
17 ms |
34916 KB |
Memory limit exceeded |
| 3 |
Runtime error |
61 ms |
49224 KB |
Memory limit exceeded |
| 4 |
Runtime error |
79 ms |
57932 KB |
Memory limit exceeded |
| 5 |
Runtime error |
146 ms |
65536 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
166 ms |
65536 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
132 ms |
65536 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
156 ms |
65536 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
155 ms |
65536 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
187 ms |
65536 KB |
Execution killed with signal 11 |
