// cre: Nguyen Ngoc Hung - Train VOI 2024
#include<bits/stdc++.h>
using namespace std;
#define __nnhzzz__ signed main()
#define BIT(i,j) ((i>>j)&1LL)
#define MASK(i) (1LL<<i)
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) (int)(x).size()
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>
#define pii pair<int,int>
#define vpii vector<pii>
#define REP(i,a,b) for(int i = (a); i<=(b); ++i)
#define REPD(i,a,b) for(int i = (a); i>=(b); --i)
#define REPDIS(i,a,b,c) for(int i = (a); i<=(b); i+=c)
#define int ll
//-------------------------------------------------------------//
const int oo = 1e9,LOG = 20,MAXN = 1e5+7,N = 1e2+3;
const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353;
//-------------------------------------------------------------//
template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;}
template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;}
/*
----------------------------------------------------------------
END OF TEMPLATE
----------------------------------------------------------------
Nguyen Ngoc Hung - nnhzzz
Training for VOI24 gold medal
----------------------------------------------------------------
*/
struct Line{
int m,b;
Line(){}
Line(int _m, int _b):m(_m),b(_b){}
ld isect(const Line &other){ return (ld)(other.b-b)/(ld)(m-other.m);}
int get(int x){ return m*x+b;}
}st[MAXN];
int dp[MAXN],S[MAXN],V[MAXN];
vpii adj[MAXN];
int top = 0;
int add(Line x){
int l = 1,r = top+1;
while(l<r){
int mid = l+(r-l)/2;
if(mid>1 && st[mid].isect(x)<=st[mid].isect(st[mid-1])){
r = mid;
}else{
l = mid+1;
}
}
return l;
}
int query(int x){
int l = 1,r = top;
while(l<r){
int mid = l+(r-l+1)/2;
if(st[mid].isect(st[mid-1])<=x){
l = mid;
}else{
r = mid-1;
}
}
return st[l].get(x);
}
void dfs(int u, int par, int h){
Line preline; int pretop = 0;
if(u==0){
dp[u] = 0; st[++top] = Line(0,0);
}else{
dp[u] = query(V[u])+S[u]+V[u]*h;
Line todo = Line(-h,dp[u]);
int pos = add(todo);
preline = st[pos]; pretop = top;
top = pos; st[top] = todo;
}
for(auto [v,w]:adj[u]){
if(v==par){
continue;
}
dfs(v,u,h+w);
}
if(u!=0){
st[top] = preline;
top = pretop;
}
}
void solve(){
int n; cin >> n;
REP(i,2,n){
int u,v,w; cin >> u >> v >> w;
--u; --v;
adj[u].emplace_back(v,w);
adj[v].emplace_back(u,w);
}
REP(i,1,n-1){
cin >> S[i] >> V[i];
}
dfs(0,0,0);
REP(i,1,n-1){
cout << dp[i] << " ";
}
}
__nnhzzz__{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#define name "test"
if(fopen(name".inp","r")){
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
#define name1 "nnhzzz"
if(fopen(name1".inp","r")){
freopen(name1".inp","r",stdin);
freopen(name1".out","w",stdout);
}
int test = 1;
while(test--){
solve();
}
cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n";
return 0;
}
Compilation message
harbingers.cpp: In function 'void dfs(long long int, long long int, long long int)':
harbingers.cpp:91:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
91 | for(auto [v,w]:adj[u]){
| ^
harbingers.cpp: In function 'int main()':
harbingers.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
125 | freopen(name".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
126 | freopen(name".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:130:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
130 | freopen(name1".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:131:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
131 | freopen(name1".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4700 KB |
Output is correct |
| 2 |
Correct |
2 ms |
5212 KB |
Output is correct |
| 3 |
Correct |
35 ms |
12388 KB |
Output is correct |
| 4 |
Correct |
50 ms |
16208 KB |
Output is correct |
| 5 |
Correct |
59 ms |
19664 KB |
Output is correct |
| 6 |
Correct |
70 ms |
23008 KB |
Output is correct |
| 7 |
Correct |
39 ms |
13140 KB |
Output is correct |
| 8 |
Correct |
92 ms |
18536 KB |
Output is correct |
| 9 |
Correct |
101 ms |
20180 KB |
Output is correct |
| 10 |
Correct |
78 ms |
18628 KB |
Output is correct |
