#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
vector <pll> T[101010];
ll P[101010][22];
pll S[101010];
ll D[101010], A[101010], B[101010];
ll n;
void insert(ll p, ll r, ll a, ll b)
{
ll i, a1, a2, b1, b2;
S[p] = pll(a, b);
for(i=16; i>=0; i--){
if(P[r][i] == P[P[r][i]][0]) continue;
tie(a1, b1) = S[P[r][i]];
tie(a2, b2) = S[P[P[r][i]][0]];
if((ld)(b2 - b) / (a - a2) < (ld)(b2 - b1) / (a1 - a2)){
r = P[P[r][i]][0];
}
}
if(r != P[r][0]){
tie(a1, b1) = S[r];
tie(a2, b2) = S[P[r][0]];
if((ld)(b2 - b) / (a - a2) < (ld)(b2 - b1) / (a1 - a2)){
r = P[r][0];
}
}
P[p][0] = r;
for(i=1; i<=16; i++){
P[p][i] = P[P[p][i - 1]][i - 1];
}
}
ll getval(ll p, ll x)
{
ll i, ret, a1, a2, b1, b2;
ret = S[p].first * x + S[p].second;
for(i=16; i>=0; i--){
if(P[p][i] == P[P[p][i]][0]) continue;
tie(a1, b1) = S[P[p][i]];
tie(a2, b2) = S[P[P[p][i]][0]];
if(a1 * x + b1 > a2 * x + b2){
p = P[p][i];
}
}
p = P[p][0];
ret = min(ret, S[p].first * x + S[p].second);
return ret;
}
void dfs(ll p, ll r, ll d)
{
D[p] = A[p] + B[p] * d + getval(r, B[p]);
insert(p, r, -d, D[p]);
for(pll &t: T[p]){
if(t.first != r){
dfs(t.first, p, d + t.second);
}
}
}
int main()
{
ll i, u, v, c;
scanf("%lld", &n);
for(i=1; i<n; i++){
scanf("%lld%lld%lld", &u, &v, &c);
T[u].emplace_back(v, c);
T[v].emplace_back(u, c);
}
for(i=2; i<=n; i++){
scanf("%lld%lld", A + i, B + i);
}
dfs(1, 0, 1);
for(i=2; i<=n; i++){
printf("%lld ", D[i]);
}
printf("\n");
return 0;
}
Compilation message
harbingers.cpp: In function 'int main()':
harbingers.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &n);
~~~~~^~~~~~~~~~~~
harbingers.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld", &u, &v, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", A + i, B + i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
8 ms |
3576 KB |
Output is correct |
3 |
Correct |
93 ms |
15836 KB |
Output is correct |
4 |
Correct |
142 ms |
22108 KB |
Output is correct |
5 |
Correct |
173 ms |
28368 KB |
Output is correct |
6 |
Runtime error |
196 ms |
34552 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
7 |
Correct |
115 ms |
22824 KB |
Output is correct |
8 |
Correct |
286 ms |
32284 KB |
Output is correct |
9 |
Runtime error |
278 ms |
33036 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
10 |
Correct |
250 ms |
32112 KB |
Output is correct |