#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
/*
--> Author: Kazuki_Hoshino__8703 <--
I love Nanasaki Ai ☆*: .。. o(≒＿≒)o .。.:☆
*/
#define fi first
#define se second
#define pii pair<int, ll>
#define ll long long
using namespace std;
const int mn = 1e5 + 5, bm = (1 << 15) + 1, mod = 1532023;
const double inf = 1e18;
int n, h[mn];
ll s[mn], v[mn];
vector <pii> a[mn];
double d[mn], dp[mn];
struct line{ double a, b; };
vector <line> reina;
vector <double> pts;
double center(line x, line y){
return (double)(x.b - y.b) / (double)(y.a - x.a);
}
struct mov{
line x;
double pts;
int add;
};
vector <mov> moves;
void add(line x){
while(reina.size() && reina.back().a == x.a && reina.back().b > x.b){
moves.push_back({reina.back(), pts.back(), -1});
reina.pop_back();
pts.pop_back();
}
while(reina.size() >= 2 && center(x, reina.back()) <= pts.back()){;
moves.push_back({reina.back(), pts.back(), -1});
reina.pop_back();
pts.pop_back();
}
if(reina.size()) pts.push_back(center(x, reina.back()));
else pts.push_back(-inf);
reina.push_back(x);
moves.push_back({x, pts.back(), 1});
}
void rollback(int snap){
while((int)moves.size() > snap){
int add = moves.back().add;
line kumiko = moves.back().x;
double y = moves.back().pts;
moves.pop_back();
if(add == 1){
reina.pop_back();
pts.pop_back();
}
else{
reina.push_back(kumiko);
pts.push_back(y);
}
}
}
ll val(ll x){
int id = upper_bound(pts.begin(), pts.end(), (double)x) - pts.begin() - 1;
return reina[id].a * x + reina[id].b;
}
void dfs(int u, int p){
int snapshot = moves.size();
line kumiko = {-d[u], dp[u]};
add(kumiko);
for(auto i : a[u]){
int vv; ll c; tie(vv, c) = i;
if(vv == p) continue;
h[vv] = h[u] + 1;
d[vv] = d[u] + c;
dp[vv] = val(v[vv]) + v[vv] * d[vv] + s[vv];
dfs(vv, u);
}
rollback(snapshot);
}
void solve(){
cin >> n;
for(int i = 1; i < n; i++){
int u, vv; ll c; cin >> u >> vv >> c;
a[u].push_back({vv, c});
a[vv].push_back({u, c});
}
for(int i = 2; i <= n; i++) cin >> s[i] >> v[i];
dfs(1, 0);
for(int i = 2; i <= n; i++) cout << (long long)dp[i] << ' ';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t = 1;
// cin >> t;
while(t--){
solve();
}
}
Compilation message (stderr)
harbingers.cpp:22:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
22 | #pragma GCC optimize("-fwhole-program")
| ^
harbingers.cpp:29:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
29 | #pragma GCC optimize("-fstrict-overflow")
| ^
harbingers.cpp:31:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
31 | #pragma GCC optimize("-fcse-skip-blocks")
| ^
harbingers.cpp:45:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
45 | #pragma GCC optimize("-funsafe-loop-optimizations")
| ^
harbingers.cpp:72:29: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
72 | double center(line x, line y){
| ^
harbingers.cpp:72:29: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
harbingers.cpp:72:29: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
harbingers.cpp:72:29: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
harbingers.cpp:84:16: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
84 | void add(line x){
| ^
harbingers.cpp:84:16: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
harbingers.cpp:84:16: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
harbingers.cpp:84:16: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
harbingers.cpp:101:23: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
101 | void rollback(int snap){
| ^
harbingers.cpp:101:23: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
harbingers.cpp:101:23: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
harbingers.cpp:101:23: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
harbingers.cpp:118:12: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
118 | ll val(ll x){
| ^
harbingers.cpp:118:12: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
harbingers.cpp:118:12: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
harbingers.cpp:118:12: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
harbingers.cpp:123:22: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
123 | void dfs(int u, int p){
| ^
harbingers.cpp:123:22: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
harbingers.cpp:123:22: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
harbingers.cpp:123:22: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
harbingers.cpp:138:12: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
138 | void solve(){
| ^
harbingers.cpp:138:12: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
harbingers.cpp:138:12: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
harbingers.cpp:138:12: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
harbingers.cpp:150:13: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
150 | signed main(){
| ^
harbingers.cpp:150:13: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
harbingers.cpp:150:13: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
harbingers.cpp:150:13: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
