# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
490888 | thiago_bastos | Harbingers (CEOI09_harbingers) | C++17 | 106 ms | 28372 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |