#include<bits/stdc++.h>
using namespace std;
#define int long long
#define forn(i,j) for(int i = 0; i < j; i++)
#define forrange(i,j,k) for(int i = j; i < k; ++i)
#define pii pair<int,int>
#define vi vector<int>
#define vpii vector<pii>
#define f first
#define pb push_back
#define s second
#define all(x) x.begin(),x.end()
const int MOD = 1e9 + 7; const int INF = 1e17 + 1; const int maxN = 2e5 + 1;
void setIO(string name = ""){
ios_base::sync_with_stdio(0);
cin.tie(0);
if(!name.empty()){
freopen((name + ".in").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
struct Line{
int m,c;
int value(int x){
return m*x + c;
}
double intersect(Line D){
return ((c - D.c)/(D.m - m));
}
};
Line L[maxN]; int V[maxN],S[maxN],dp[maxN],curr_sz = 0;
int min_val(int x){
int lo = 0; int hi = curr_sz-1;
while(lo < hi){
int mid = (lo+hi)/2;
if(L[mid].intersect(L[mid+1]) < x){
lo = mid+1;
}
else{
hi = mid;
}
}
return L[lo].value(x);
}
int pos(Line D){
if(curr_sz <= 1 || D.intersect(L[curr_sz-1]) > L[curr_sz-1].intersect(L[curr_sz-2])){
return curr_sz;
}
int lo = 1; int hi = curr_sz-1;
while(lo < hi){
int mid = (lo+hi)/2;
if(D.intersect(L[mid]) < L[mid].intersect(L[mid-1])){
hi = mid;
}
else{
lo = mid+1;
}
}
return lo;
}
vpii graph[maxN];
void dfs(int src, int prev, int d){
for(auto [ch,dist] : graph[src]){
if(ch == prev) continue;
dp[ch] = min_val(V[ch]) + V[ch]*(d+dist) + S[ch];
Line D = {-d-dist,dp[ch]};
int curr = curr_sz;
int curr_pos = curr_sz = pos(D); Line pre = L[curr_pos];
L[curr_pos] = D; curr_sz++;
dfs(ch,src,d+dist);
//reset the changes
L[curr_pos] = pre; curr_sz = curr;
}
}
signed main(){
setIO();
int n; cin >> n;
forn(i,n-1){
int a,b,c; cin >> a >> b >> c;
graph[a].pb({b,c}); graph[b].pb({a,c});
}
forrange(i,2,n+1){
cin >> S[i] >> V[i];
}
L[0] = {0,0}; curr_sz++;
dfs(1,-1,0);
forrange(i,2,n+1){
cout << dp[i] << " ";
}
}
Compilation message
harbingers.cpp: In function 'void dfs(long long int, long long int, long long int)':
harbingers.cpp:84:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
84 | for(auto [ch,dist] : graph[src]){
| ^
harbingers.cpp: In function 'void setIO(std::string)':
harbingers.cpp:22:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | freopen((name + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:23:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
23 | freopen((name + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
10844 KB |
Output is correct |
2 |
Correct |
4 ms |
11352 KB |
Output is correct |
3 |
Correct |
39 ms |
19816 KB |
Output is correct |
4 |
Correct |
55 ms |
23700 KB |
Output is correct |
5 |
Correct |
61 ms |
27984 KB |
Output is correct |
6 |
Correct |
72 ms |
31828 KB |
Output is correct |
7 |
Correct |
40 ms |
20052 KB |
Output is correct |
8 |
Correct |
87 ms |
24776 KB |
Output is correct |
9 |
Correct |
96 ms |
26732 KB |
Output is correct |
10 |
Correct |
86 ms |
25188 KB |
Output is correct |