#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned;
using i16 = short;
using u16 = unsigned short;
using ld = long double;
using ii = pair<int, int>;
using T = tuple<int, i64, i64, int>;
int n;
vector<vector<ii>> g;
vector<i64> pre, dp;
stack<T> changes;
deque<pair<i64, i64>> dq;
vector<int> s, vel;
ld point(i64 a0, i64 b0, i64 a1, i64 b1) {
return (b1 - b0) / ld(a0 - a1);
}
void dfs(int u, int p) {
while((int)dq.size() >= 2) {
auto [a0, b0] = dq[0];
auto [a1, b1] = dq[1];
if(a0 * vel[u] + b0 < a1 * vel[u] + b1) break;
changes.emplace(u, a0, b0, 0);
dq.pop_front();
}
if(u != p) dp[u] = s[u] + vel[u] * (pre[u] + dq[0].first) + dq[0].second;
while((int)dq.size() >= 2) {
int n = dq.size();
auto [a0, b0] = dq[n - 1];
auto [a1, b1] = dq[n - 2];
if(point(-pre[u], dp[u], a0, b0) > point(a0, b0, a1, b1)) break;
changes.emplace(u, a0, b0, 1);
dq.pop_back();
}
dq.emplace_back(-pre[u], dp[u]);
for(auto [v, d] : g[u]) {
if(v == p) continue;
pre[v] = pre[u] + d;
dfs(v, u);
}
dq.pop_back();
while(!changes.empty()) {
auto [_, a, b, t] = changes.top();
if(_ != u) break;
changes.pop();
if(t == 0) dq.emplace_front(a, b);
else dq.emplace_back(a, b);
}
}
void solve() {
cin >> n;
g.resize(n);
pre.resize(n);
dp.resize(n);
s.resize(n);
vel.resize(n);
for(int i = 1; i < n; ++i) {
int u, v, d;
cin >> u >> v >> d;
--u, --v;
g[u].emplace_back(v, d);
g[v].emplace_back(u, d);
}
s[0] = vel[0] = 0;
for(int i = 1; i < n; ++i) cin >> s[i] >> vel[i];
pre[0] = dp[0] = 0;
dfs(0, 0);
for(int i = 1; i < n; ++i) cout << dp[i] << ' ';
cout << '\n';
}
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(0);
int t = 1;
//cin >> t;
while(t--) solve();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
2 |
Incorrect |
2 ms |
972 KB |
Output isn't correct |
3 |
Incorrect |
34 ms |
11972 KB |
Output isn't correct |
4 |
Incorrect |
50 ms |
17448 KB |
Output isn't correct |
5 |
Incorrect |
73 ms |
23152 KB |
Output isn't correct |
6 |
Incorrect |
106 ms |
28372 KB |
Output isn't correct |
7 |
Incorrect |
50 ms |
11812 KB |
Output isn't correct |
8 |
Incorrect |
101 ms |
17652 KB |
Output isn't correct |
9 |
Incorrect |
102 ms |
21216 KB |
Output isn't correct |
10 |
Incorrect |
65 ms |
19568 KB |
Output isn't correct |