# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
377266 | jhwest2 | Harbingers (CEOI09_harbingers) | C++14 | 1096 ms | 24668 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
typedef pair<lint, lint> plint;
const int MAX = 1e5 + 10;
int n, S[MAX], V[MAX], Dist[MAX];
lint Dp[MAX];
vector<pint> G[MAX];
struct CHT {
vector<pair<int, lint>> V, Buf;
void update(int a, lint b) {
if (V.size() < 2) { V.emplace_back(a, b); return; }
while (V.size() >= 2) {
auto p = V[V.size() - 2], c = V.back();
if ((c.vb - p.vb) * (c.va - a) > (b - c.vb) * (p.va - c.va)) Buf.push_back(V.back()), V.pop_back();
else break;
}
V.emplace_back(a, b);
}
lint query(lint x) {
if (V.size() == 1) return x * V.back().va + V.back().vb;
int lo = 0, hi = V.size() - 1;
while (lo < hi) {
int mid = lo + hi >> 1;
if ((V[mid + 1].vb - V[mid].vb) < x * (V[mid].va - V[mid + 1].va)) lo = mid + 1;
else hi = mid;
}
return x * V[lo].va + V[lo].vb;
}
} C;
void dfs(int prv, int cur) {
if (cur != 1) Dp[cur] = C.query(V[cur]) + (lint)V[cur] * Dist[cur] + S[cur];
int bs = C.Buf.size();
C.update(-Dist[cur], Dp[cur]);
for (auto nxt : G[cur]) {
if (prv == nxt.vb) continue;
Dist[nxt.vb] = Dist[cur] + nxt.va;
dfs(cur, nxt.vb);
}
C.V.pop_back();
while (C.Buf.size() > bs) C.V.push_back(C.Buf.back()), C.Buf.pop_back();
}
int main() {
cin.tie(0); ios_base::sync_with_stdio(0);
cin >> n;
for (int i = 1; i < n; i++) {
int x, y, w; cin >> x >> y >> w;
G[x].emplace_back(w, y); G[y].emplace_back(w, x);
}
for (int i = 2; i <= n; i++) cin >> S[i] >> V[i];
dfs(0, 1);
for (int i = 2; i <= n; i++) cout << Dp[i] << ' ';
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |