#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int N;
vector<vector<LL>> cht((int)1e5, vector<LL>(3));
vector<vector<vector<LL>>> era((int)1e5);
int top, etop;
vector<vector<LL>> imsi((int)1e5);
int tt;
inline LL getc(vector<LL> A, vector<LL> B){
return (B[2] - A[2]) / (A[1] - B[1]) + ((B[2] - A[2]) % (A[1] - B[1]) > 0);
}
void push(LL A, LL B){
cht[top++] = {-(LL)1e18, A, B};
if(top >= 2){
cht[top - 1][0] = getc(cht[top - 2], cht[top - 1]);
}
tt = 0;
while(top >= 3 && cht[top - 1][0] <= cht[top - 2][0]){
imsi[tt++] = cht[top - 2];
cht[top - 2] = cht[top - 1]; --top;
cht[top - 1][0] = getc(cht[top - 2], cht[top - 1]);
}
vector<vector<LL>> np(tt);
for(int i = 0; i < tt; ++i){
np[i] = imsi[i];
}
era[etop++] = np;
}
LL get(LL x){
vector<LL> vc = {x + 1, -(LL)1e18, -(LL)1e18};
int pos = lower_bound(cht.begin(), cht.begin() + top, vc) - cht.begin() - 1;
return cht[pos][1] * x + cht[pos][2];
}
void del(){
--top;
vector<vector<LL>> now = era[--etop];
for(int i = (int)now.size() - 1; i >= 0; --i){
cht[top++] = now[i];
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N;
vector<vector<pair<int, int>>> way(N);
for(int i = 0; i < N - 1; ++i){
int a, b, c; cin >> a >> b >> c; --a; --b;
way[a].push_back({b, c}), way[b].push_back({a, c});
}
vector<pair<int, int>> val(N);
for(int i = 1; i < N; ++i){
cin >> val[i].first >> val[i].second;
}
vector<LL> sum(N), chk(N), dp(N);
function<void(int, int)> dfs = [&](int x, int dis){
chk[x] = 1;
sum[x] = dis;
if(x){
dp[x] = get(val[x].second) + val[x].first + val[x].second * sum[x];
}
else dp[x] = 0;
push(-sum[x], dp[x]);
for(auto&nxt:way[x]){
if(!chk[nxt.first]){
dfs(nxt.first, dis + nxt.second);
}
}
del();
};
dfs(0, 0);
for(int i = 1; i < N; ++i){
cout << dp[i] << ' ';
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
10476 KB |
Output is correct |
2 |
Correct |
13 ms |
10988 KB |
Output is correct |
3 |
Correct |
89 ms |
19332 KB |
Output is correct |
4 |
Correct |
105 ms |
23020 KB |
Output is correct |
5 |
Correct |
153 ms |
28012 KB |
Output is correct |
6 |
Correct |
208 ms |
32276 KB |
Output is correct |
7 |
Correct |
114 ms |
21136 KB |
Output is correct |
8 |
Execution timed out |
1086 ms |
29776 KB |
Time limit exceeded |
9 |
Execution timed out |
1075 ms |
23276 KB |
Time limit exceeded |
10 |
Execution timed out |
1094 ms |
33192 KB |
Time limit exceeded |