#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
struct line{
int32_t m;int n;
line(int32_t m,int n):m(m),n(n){}
line(){}
int operator()(int x) const{
return m*x+n;
}
};
struct node{
int32_t left,right;
int32_t L,R;
int32_t lin;
node(){}
node(int32_t L,int32_t R): L(L), R(R), left(-1), right(-1), lin(0){}
};
line lines[100001];
node nodes[1500001];
int32_t c;
int query(node* curr,int x){
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), curr->right==-1 ? INF : query(&nodes[curr->right], x));
return min(lines[curr->lin](x), curr->left==-1 ? INF : query(&nodes[curr->left], x));
}
void update(node* curr,int32_t x, vector<pair<node*,int32_t>> &updates){
int32_t 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==-1) {
nodes[++c] = node(curr->L, mid - 1);
curr->left = c;
}
update(&nodes[curr->left],x,updates);
} else if(!bettermid){
if(curr->right==-1) {
nodes[++c] = node(mid+1, curr->R);
curr->right = c;
}
update(&nodes[curr->right],x,updates);
} else if(betterleft){
updates.emplace_back(curr,curr->lin);
swap(curr->lin,x);
if(curr->right==-1) {
nodes[++c] = node(mid+1, curr->R);
curr->right = c;
}
update(&nodes[curr->right],x,updates);
} else {
updates.emplace_back(curr,curr->lin);
swap(curr->lin, x);
if(curr->left==-1) {
nodes[++c] = node(curr->L, mid - 1);
curr->left = c;
}
update(&nodes[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,int 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(int32_t 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:20:15: warning: 'node::R' will be initialized after [-Wreorder]
20 | int32_t L,R;
| ^
harbingers.cpp:19:13: warning: 'int32_t node::left' [-Wreorder]
19 | int32_t left,right;
| ^~~~
harbingers.cpp:23:5: warning: when initialized here [-Wreorder]
23 | node(int32_t L,int32_t R): L(L), R(R), left(-1), right(-1), lin(0){}
| ^~~~
harbingers.cpp: In function 'void dfs(int32_t, int32_t, long long int)':
harbingers.cpp:96: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]
96 | while(updates.size()>old_len){
| ~~~~~~~~~~~~~~^~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4696 KB |
Output is correct |
2 |
Correct |
4 ms |
5340 KB |
Output is correct |
3 |
Correct |
72 ms |
17328 KB |
Output is correct |
4 |
Runtime error |
130 ms |
43408 KB |
Memory limit exceeded |
5 |
Correct |
114 ms |
20932 KB |
Output is correct |
6 |
Correct |
151 ms |
20440 KB |
Output is correct |
7 |
Correct |
96 ms |
14016 KB |
Output is correct |
8 |
Correct |
167 ms |
31280 KB |
Output is correct |
9 |
Runtime error |
174 ms |
50096 KB |
Memory limit exceeded |
10 |
Correct |
154 ms |
31912 KB |
Output is correct |