/*
* File created on 01/08/2022 at 10:53:58.
* Link to problem:
* Description:
* Time complexity: O()
* Space complexity: O()
* Status: ---
* Copyright: Ⓒ 2022 Francois Vogel
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
using namespace std;
using namespace __gnu_pbds;
#define pii pair<int, int>
#define f first
#define s second
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define size(x) (int)((x).size())
#define pb push_back
#define ins insert
#define cls clear
#define int ll
#define ll long long
#define ld long double
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int siz = 1e5+40;
const int inf = 1e18;
vector<pii> graph [siz];
int height [siz];
int dp [siz];
int prep [siz];
int speed [siz];
map<ld, int> opt;
vi q;
ld xIntercept(int a1, int b1, int a2, int b2) {
if (a1-a2 == 0) return (ld)(b2-b1)*(ld)(inf);
return (ld)(b2-b1)/(ld)(a1-a2);
}
void dfs(int x, int p = -1) {
if (p == -1) dp[x] = 0;
else {
auto it = opt.upper_bound(speed[x]);
it = prev(it);
dp[x] = -height[(*it).s]*speed[x]+dp[(*it).s];
dp[x] += height[x]*speed[x]+prep[x];
}
vector<pair<ld, int>> rem;
// while (size(q) >= 2 && xIntercept(-height[q.back()], dp[q.back()], -height[q[size(q)-2]], dp[q[size(q)-2]]) >= xIntercept(-height[x], dp[x], -height[q.back()], dp[q.back()])) {
// rem.pb(*(prev(opt.end())));
// opt.erase(prev(opt.end()));
// q.pop_back();
// }
// reverse(all(rem)); // first in rem is now deepest in stack q
ld fromX = -inf;
if (!q.empty()) {
fromX = ceil(xIntercept(-height[x], dp[x], -height[q.back()], dp[q.back()]));
}
opt[fromX] = x;
q.pb(x);
for (pii y : graph[x]) if (y.f != p) {
height[y.f] = height[x]+y.s;
dfs(y.f, x);
}
// q.pop_back();
// opt.erase(prev(opt.end()));
// for (pair<ld, int> i : rem) {
// q.pb(i.s);
// opt[i.f] = i.s;
// }
}
signed main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
int n;
cin >> n;
for (int i = 0; i < n-1; i++) {
int na, nb, lw;
cin >> na >> nb >> lw;
na--;
nb--;
graph[na].pb(pii(nb, lw));
graph[nb].pb(pii(na, lw));
}
for (int i = 1; i < n; i++) cin >> prep[i] >> speed[i];
dfs(0);
for (int i = 1; i < n; i++) cout << dp[i] << ' ';
cout.flush();
int d = 0;
d++;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2636 KB |
Output isn't correct |
| 2 |
Incorrect |
4 ms |
3276 KB |
Output isn't correct |
| 3 |
Incorrect |
58 ms |
13188 KB |
Output isn't correct |
| 4 |
Incorrect |
77 ms |
15744 KB |
Output isn't correct |
| 5 |
Incorrect |
141 ms |
23512 KB |
Output isn't correct |
| 6 |
Incorrect |
159 ms |
28400 KB |
Output isn't correct |
| 7 |
Incorrect |
100 ms |
17124 KB |
Output isn't correct |
| 8 |
Incorrect |
143 ms |
24024 KB |
Output isn't correct |
| 9 |
Incorrect |
146 ms |
25140 KB |
Output isn't correct |
| 10 |
Incorrect |
135 ms |
24076 KB |
Output isn't correct |
