#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int sz=1e6+10;
const long long inf=1e17 - 200000;
const int mod = 1e9 + 7;
typedef pair<long long,long long>info;
int n,k,m,q,dis,lim;
ll timer=1;
long long d[sz];
long long dp[sz];
vector<pair<long long,long long>>adj[sz];
pair<long long,long long>lines[sz];
vector<pair<info,info>>lst;
struct harbinger{
long long s,v;
}a[sz];
long long query(long long x){
int l = 0; int r = lim - 1;
long long ans = lines[0].first*x + lines[0].second;
while(l <= r){
int mid = (l + r)>>1;
long long lval = lines[mid].first*x + lines[mid].second;
long long rval = lines[mid + 1].first*x + lines[mid + 1].second;
if(lval > rval) l = mid +1;
else r = mid - 1;
ans = min(ans,min(lval,rval));
}
return ans;
}
bool check(info &a,info &b,info &c){
return (c.first - a.first)*(a.second - b.second) > (b.first - a.first)*(a.second - c.second);
}
void add_line(info line){
int l = 1; int r = lim - 1; int k = lim;
while(l <= r){
int mid = (l + r)>>1;
if(check(lines[mid - 1],lines[mid],line)){
r = mid - 1;
k = mid;
}
else l = mid + 1;
}
lst.push_back({{k,lim},lines[k]});
lines[k] = line;
lim = k + 1;
}
void dfs(int u,int p){
if(u != 1) dp[u] = (1ll)*a[u].v*d[u] + a[u].s + query(a[u].v);
add_line(make_pair(-d[u],dp[u]));
for(int i = 0; i < adj[u].size(); i++){
pair<long long,long long>v = adj[u][i];
if(v.first == p) continue;
d[v.first] = d[u] + v.second;
dfs(v.first,u);
}
pair<info,info>cur = lst.back();
lst.pop_back();
lines[cur.first.first] = cur.second;
lim = cur.first.second;
}
int main(){
scanf("%d",&n);
for(int i = 1; i < n; i++){
long long u,v,w; scanf("%lld%lld%lld",&u,&v,&w);
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
for(int i = 2; i <= n; i++){
scanf("%lld%lld",&a[i].s,&a[i].v);
}
dfs(1,0);
for(int i = 2; i <= n; i++) cout<<dp[i]<<' ';
}
Compilation message
harbingers.cpp: In function 'void dfs(int, int)':
harbingers.cpp:51:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for(int i = 0; i < adj[u].size(); i++){
| ~~^~~~~~~~~~~~~~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:63:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
harbingers.cpp:65:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | long long u,v,w; scanf("%lld%lld%lld",&u,&v,&w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:70:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | scanf("%lld%lld",&a[i].s,&a[i].v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
12 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
15 ms |
24420 KB |
Output is correct |
| 3 |
Runtime error |
50 ms |
33068 KB |
Memory limit exceeded |
| 4 |
Runtime error |
71 ms |
37208 KB |
Memory limit exceeded |
| 5 |
Runtime error |
96 ms |
41100 KB |
Memory limit exceeded |
| 6 |
Runtime error |
140 ms |
44944 KB |
Memory limit exceeded |
| 7 |
Runtime error |
93 ms |
34440 KB |
Memory limit exceeded |
| 8 |
Runtime error |
118 ms |
40432 KB |
Memory limit exceeded |
| 9 |
Runtime error |
158 ms |
42352 KB |
Memory limit exceeded |
| 10 |
Runtime error |
100 ms |
40556 KB |
Memory limit exceeded |
