#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define f first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
using namespace std;
const int N = 1e5 + 123;
const ll mod = 1e9 + 7;
const ll inf = 1e18;
struct line {
ll k, b;
};
struct node {
node *l, *r;
line cur;
node (node *v, line x) {
if (!v) {
cur = x;
l = NULL;
r = NULL;
} else {
cur = v->cur;
l = v->l;
r = v->r;
}
}
};
node *t[N];
ll lb, rb;
ld getld(line cur, ll x) {
x *= 1.0;
return cur.k * 1.0 * x + cur.b * 1.0;
}
ll getll(line cur, ll x) {
return cur.k * x + cur.b;
}
ll getmid(ll tl, ll tr) {
return ((tl + tr + 2ll * inf) / 2ll) - inf;
}
void add(node *&v, ll tl, ll tr, line nw) {
if (!v) {
v = new node(v, nw);
return;
}
v = new node(v, nw);
ll tm = getmid(tl, tr);
bool left = getld(v->cur, tl) > getld(nw, tl);
bool mid = getld(v->cur, tm) > getld(nw, tm);
bool right = getld(v->cur, tr) > getld(nw, tr);
if ((left && mid) || (right && mid))
swap(v->cur, nw);
if (tl == tr) return;
if (left == mid)
add(v->r, tm + 1, tr, nw);
else
add(v->l, tl, tm, nw);
}
ll get(node *&v, ll tl, ll tr, ll x) {
if (!v) return inf;
if (tl == tr) return getll(v->cur, x);
ll res, tm = getmid(tl, tr);
if (x <= tm)
res = get(v->l, tl, tm, x);
else
res = get(v->r, tm + 1, tr, x);
return min(res, getll(v->cur, x));
}
void clearr(node *&v) {
if (!v) return;
clearr(v->l);
clearr(v->r);
v = NULL;
}
ll n, s[N], v[N], dp[N];
vector <pll> g[N];
void dfs(ll u, ll p, ll d) {
line tmp;
dp[u] = s[u] + v[u] * d + get(t[p], lb, rb, v[u]);
tmp.k = -d; tmp.b = dp[u];
t[u] = t[p];
add(t[u], lb, rb, tmp);
for (pll to : g[u])
if (to.f != p)
dfs(to.f, u, d + to.se);
}
int main() {
ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
//freopen("input.txt", "r", stdin);
// freopen("harbingers.in", "r", stdin);
// freopen("harbingers.out", "w", stdout);
line tmp;
lb = 0; rb = 1000000010;
cin >> n;
for (int i = 1; i < n; i++) {
ll u, v, d;
cin >> u >> v >> d;
g[u].pb({v, d});
g[v].pb({u, d});
}
for (int i = 2; i <= n; i++)
cin >> s[i] >> v[i];
dp[1] = 0;
tmp.k = 0; tmp.b = 0;
add(t[1], lb, rb, tmp);
for (pll to : g[1])
dfs(to.f, 1, to.se);
for (int i = 2; i <= n; i++)
cout << dp[i] << " ";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
2680 KB |
Output is correct |
| 2 |
Correct |
12 ms |
6392 KB |
Output is correct |
| 3 |
Runtime error |
144 ms |
59204 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
| 4 |
Runtime error |
173 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
186 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
194 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
169 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
213 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
210 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
187 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
