/// [_DukkSooCee3305_]
/// Date : 05/10/2021
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define ALL(i_) i_.begin(), i_.end()
#define Random(lf_, rt_) (lf_ + rand() % (rt_ - lf_ + 1))
#define PB push_back
#define sz(i_) ((int)(i_).size())
#define reset(i_, x_) memset(i_, x_, sizeof i_)
#define TASK "HARBINGERS"
typedef long long ll;
typedef long double ld;
typedef pair<int, ll> ii;
const int oo = 1000000099;
const int mod = 1000000007;
const int maxn = 100011;
int n;
vector<ii> ke[maxn];
int t[maxn], g[maxn], d[maxn];
ll dp[maxn];
struct line{
ll a, b;
ll f(ll x){ return (a*x + b); };
};
struct CHT{
deque<line> dq;
vector<line> undoList[maxn];
ld slope(line l1, line l2){
return (ld) (l2.b - l1.b) / (ld) (l2.a - l1.a);
}
bool better(line new_line, line a, line b){
return (slope(new_line, a) <= slope(new_line, b));
}
void add_line(int pos, line new_line){
while(sz(dq) >= 2 && better(new_line, dq[sz(dq) - 2], dq.back())) dq.pop_back();
dq.push_back(new_line);
FOR(i, 0, sz(dq) - 1){
undoList[pos].PB(dq[i]);
}
}
ll get_values(ll x){
if(sz(dq) == 1) return dq[0].f(x);
int lf = 0, rt = sz(dq) - 1;
ll res = dq[lf].f(x);
while(rt - lf >= 0){
int mid = (rt - lf)/2 + lf;
ll f1 = dq[mid].f(x);
ll f2 = dq[mid + 1].f(x);
if(f1 > f2) lf = mid + 1;
else rt = mid - 1;
res = min(res, min(f1, f2));
}
return res;
}
void undo(int u){
while(!dq.empty()) dq.pop_back();
FOR(i, 0, sz(undoList[u]) - 1) dq.push_back(undoList[u][i]);
}
} convex_hull;
namespace process{
void DFS(int u, int par){
if(u > 1){
dp[u] = t[u] + g[u] * d[u];
dp[u] += convex_hull.get_values(g[u]);
}
convex_hull.add_line(u, {-d[u], dp[u]});
for(ii x : ke[u]){
int v = x.first;
ll w = x.second;
if(v == par) continue;
d[v] = d[u] + w;
DFS(v, u);
convex_hull.undo(u);
}
}
void solve(){
d[1] = 0;
dp[1] = 0;
DFS(1, -1);
FOR(i, 2, n) cout << dp[i] << " ";
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout);
cin >> n;
FOR(i, 1, n-1){
int u, v;
ll w;
cin >> u >> v >> w;
ke[u].PB({v, w});
ke[v].PB({u, w});
}
FOR(i, 2, n) cin >> t[i] >> g[i];
process::solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
4940 KB |
Output isn't correct |
2 |
Correct |
5 ms |
5836 KB |
Output is correct |
3 |
Incorrect |
53 ms |
15212 KB |
Output isn't correct |
4 |
Incorrect |
92 ms |
23628 KB |
Output isn't correct |
5 |
Incorrect |
114 ms |
24348 KB |
Output isn't correct |
6 |
Runtime error |
184 ms |
45276 KB |
Memory limit exceeded |
7 |
Incorrect |
80 ms |
18072 KB |
Output isn't correct |
8 |
Incorrect |
150 ms |
24984 KB |
Output isn't correct |
9 |
Incorrect |
132 ms |
26296 KB |
Output isn't correct |
10 |
Runtime error |
100 ms |
65540 KB |
Execution killed with signal 9 |