#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long lint;
typedef pair<int,int> pi;
typedef pair<lint,lint> pii;
vector<pi> graph[100005];
int n, s[100005], v[100005];
lint dp[100005];
pii stk[100005];
inline lint func(pii x, int t){
return x.first * t + x.second;
}
inline bool cross(pii a, pii b, pii c){
return (1.0 * (b.second - a.second) / (a.first - b.first) >= 1.0 * (c.second - b.second) / (b.first - c.first));
}
void process(int x, int& piv, int dist){
int st, ed, m;
if(x != 1){
st = 0, ed = piv - 1;
while (st != ed){
m = (st + ed)/2;
if(func(stk[m],v[x]) <= func(stk[m+1],v[x])){
ed = m;
}
else st = m+1;
}
dp[x] = func(stk[st],v[x]) + 1ll * dist * v[x] + s[x];
}
pii tmp = pii(-dist,dp[x]);
st = 0, ed = piv-1;
while (st < ed){
m = (st + ed) / 2;
if(cross(stk[m],stk[m+1],tmp)){
ed = m;
}
else st = m+1;
}
piv = ed + 1;
}
void solve(int x, int piv, int pa, int dist){
process(x,piv,dist);
pii bk = stk[piv];
stk[piv] = pii(-dist,dp[x]);
for (int i=0; i<graph[x].size(); i++) {
if(graph[x][i].second != pa){
solve(graph[x][i].second,piv+1,x,dist + graph[x][i].first);
}
}
stk[piv] = bk;
}
int main(){
scanf("%d",&n);
for (int i=0; i<n-1; i++) {
int s,e,x;
scanf("%d %d %d",&s,&e,&x);
graph[s].push_back(pi(x,e));
graph[e].push_back(pi(x,s));
}
for (int i=2; i<=n; i++) {
scanf("%d %d",&s[i],&v[i]);
}
solve(1,0,0,0);
for (int i=2; i<=n; i++) {
printf("%lld ",dp[i]);
}
}
Compilation message
harbingers.cpp: In function 'void solve(int, int, int, int)':
harbingers.cpp:53:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i=0; i<graph[x].size(); i++) {
~^~~~~~~~~~~~~~~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
harbingers.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&s,&e,&x);
~~~~~^~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&s[i],&v[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
6 ms |
2936 KB |
Output is correct |
3 |
Correct |
61 ms |
8388 KB |
Output is correct |
4 |
Correct |
91 ms |
11396 KB |
Output is correct |
5 |
Correct |
109 ms |
13664 KB |
Output is correct |
6 |
Correct |
135 ms |
15992 KB |
Output is correct |
7 |
Correct |
81 ms |
9080 KB |
Output is correct |
8 |
Correct |
149 ms |
12660 KB |
Output is correct |
9 |
Correct |
152 ms |
14456 KB |
Output is correct |
10 |
Correct |
133 ms |
13684 KB |
Output is correct |