#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);
if(c == 0) for(; ; );
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:91: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 |
7 ms |
3576 KB |
Output is correct |
3 |
Correct |
91 ms |
15992 KB |
Output is correct |
4 |
Correct |
150 ms |
22136 KB |
Output is correct |
5 |
Correct |
152 ms |
28280 KB |
Output is correct |
6 |
Runtime error |
193 ms |
34524 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
7 |
Correct |
114 ms |
22780 KB |
Output is correct |
8 |
Correct |
279 ms |
32260 KB |
Output is correct |
9 |
Runtime error |
272 ms |
32940 KB |
Memory limit exceeded (if you are sure your verdict is not MLE, please contact us) |
10 |
Correct |
244 ms |
32112 KB |
Output is correct |