#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
struct line{
int32_t m;int n;
line(int m,int n):m(m),n(n){}
line(){}
int operator()(int x) const{
return m*x+n;
}
};
struct node{
node *left,*right;
int32_t L,R;
int32_t lin;
node(int32_t L,int32_t R): L(L), R(R), left(nullptr), right(nullptr), lin(0){}
};
line lines[100001];
int query(node* curr,int x){
if(curr==nullptr)return INF;
int32_t mid = (curr->L+curr->R)/2;
if(mid==x)return lines[curr->lin](x);
if(mid<x)return min(lines[curr->lin](x), query(curr->right, x));
return min(lines[curr->lin](x), query(curr->left, x));
}
void update(node* curr,int32_t x, vector<pair<node*,int32_t>> &updates){
int mid = (curr->L+curr->R)/2;
bool betterleft = lines[curr->lin](curr->L) > lines[x](curr->L);
bool betterright = lines[curr->lin](curr->R) > lines[x](curr->R);
bool bettermid = lines[curr->lin](mid) > lines[x](mid);
if(!(betterleft or bettermid or betterright))return;
if(bettermid and betterright and betterleft) {
updates.emplace_back(curr,curr->lin);
swap(x, curr->lin);
}
else if(betterleft and !bettermid){
if(curr->left==nullptr)curr->left = new node(curr->L,mid-1);
update(curr->left,x,updates);
} else if(!bettermid){
if(curr->right==nullptr)curr->right = new node(mid+1,curr->R);
update(curr->right,x,updates);
} else if(betterleft){
updates.emplace_back(curr,curr->lin);
swap(curr->lin,x);
if(curr->right==nullptr)curr->right = new node(mid+1,curr->R);
update(curr->right,x,updates);
} else {
updates.emplace_back(curr,curr->lin);
swap(curr->lin, x);
if(curr->left==nullptr)curr->left = new node(curr->L,mid-1);
update(curr->left,x,updates);
}
}
int DP[100001];
int32_t S[100001];
int32_t V[100001];
vector<pair<int32_t,int32_t>> adj[100001];
node* head = new node(1,1e9);
vector<pair<node*,int32_t>> updates;
void dfs(int32_t x,int32_t p,int32_t depth){
DP[x] = S[x]+V[x]*depth+ query(head,V[x]);
int32_t old_len = updates.size();
lines[x] = line(-depth,DP[x]);
update(head,x,updates);
for(auto&i:adj[x])if(i.first!=p){
dfs(i.first,x,depth+i.second);
}
while(updates.size()>old_len){
updates.back().first->lin = updates.back().second;
updates.erase(--updates.end());
}
}
int32_t main(){
// freopen("harbingers.in","r",stdin);
// freopen("harbingers.out","w",stdout);
int32_t n;
cin >> n;
for(int32_t i=1;i<n;i++){
int32_t u,v,d;cin>>u>>v>>d;
adj[u].emplace_back(v,d);
adj[v].emplace_back(u,d);
}
for(int32_t i=2;i<=n;i++)cin>>S[i]>>V[i];
lines[0] = line(0,0);
update(head,0,updates);
dfs(1,0,0);
for(int i=2;i<n;i++)cout<<DP[i]<<' ';
cout << DP[n] << '\n';
}
Compilation message
harbingers.cpp: In constructor 'node::node(int32_t, int32_t)':
harbingers.cpp:19:15: warning: 'node::R' will be initialized after [-Wreorder]
19 | int32_t L,R;
| ^
harbingers.cpp:18:11: warning: 'node* node::left' [-Wreorder]
18 | node *left,*right;
| ^~~~
harbingers.cpp:21:5: warning: when initialized here [-Wreorder]
21 | node(int32_t L,int32_t R): L(L), R(R), left(nullptr), right(nullptr), lin(0){}
| ^~~~
harbingers.cpp: In function 'void dfs(int32_t, int32_t, int32_t)':
harbingers.cpp:81:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<node*, int> >::size_type' {aka 'long unsigned int'} and 'int32_t' {aka 'int'} [-Wsign-compare]
81 | while(updates.size()>old_len){
| ~~~~~~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5212 KB |
Output is correct |
| 3 |
Incorrect |
58 ms |
10192 KB |
Output isn't correct |
| 4 |
Incorrect |
79 ms |
13328 KB |
Output isn't correct |
| 5 |
Incorrect |
108 ms |
15812 KB |
Output isn't correct |
| 6 |
Correct |
137 ms |
19904 KB |
Output is correct |
| 7 |
Incorrect |
101 ms |
11216 KB |
Output isn't correct |
| 8 |
Incorrect |
126 ms |
14428 KB |
Output isn't correct |
| 9 |
Incorrect |
131 ms |
16064 KB |
Output isn't correct |
| 10 |
Incorrect |
130 ms |
17596 KB |
Output isn't correct |
