# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
993566 | efishel | Harbingers (CEOI09_harbingers) | C++17 | 130 ms | 65536 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vll = vector <ll>;
const ll MAXN = 1E5+16, INF = ll(1E18)+16;
vector <pair <ll, ll> > adj[MAXN];
ll dp[MAXN];
ll dis[MAXN];
ll sleep[MAXN], slow[MAXN];
#define mid ((l+r)>>1)
struct SegTree {
struct Fun {
ll a, b;
ll operator() (ll x) const { return a*x + b; }
};
SegTree *left, *right;
ll l, r;
Fun f;
SegTree (ll l, ll r): left(0), right(0), l(l), r(r), f({0, INF}) {}
void update (Fun g, vector <vector <pair <SegTree*, SegTree::Fun> > > &ups) {
bool isL = g(l) < f(l);
bool isM = g(mid) < f(mid);
if (isM) {
ups.back().push_back({ this, f });
swap(f, g);
}
if (l == r || g.a == 0 && g.b == INF) return;
if (isL != isM) {
if (!left) left = new SegTree(l, mid);
left->update(g, ups);
} else {
if (!right) right = new SegTree(mid+1, r);
right->update(g, ups);
}
}
ll query (ll x) {
if (x <= mid)
return min(f(x), left ? left->query(x) : INF);
else
return min(f(x), right ? right->query(x) : INF);
}
} st(0, 1E9);
vector <vector <pair <SegTree*, SegTree::Fun> > > ups;
void rollback () {
auto th = ups.back(); ups.pop_back();
for (auto [stPtr, lastFun] : th) {
stPtr->f = lastFun;
}
}
vll stk;
void dfs (ll u, ll par) {
dp[u] = sleep[u]+slow[u]*dis[u];
dp[u] = min(dp[u], st.query(slow[u]) +sleep[u]+slow[u]*dis[u]);
ups.push_back({});
st.update({-dis[u], dp[u]}, ups);
for (auto [v, w] : adj[u]) {
if (v == par) continue;
dis[v] = dis[u]+w;
dfs(v, u);
}
rollback();
}
int main () {
cin.tie(nullptr) -> sync_with_stdio(false);
ll n;
cin >> n;
for (ll i = 1; i < n; i++) {
ll u, v, w;
cin >> u >> v >> w;
u--; v--;
adj[u].push_back({ v, w });
adj[v].push_back({ u, w });
}
for (ll i = 1; i < n; i++) cin >> sleep[i] >> slow[i];
dis[0] = 0;
dp[0] = 0;
dfs(0, 0);
for (ll i = 1; i < n; i++) cout << dp[i] << ' ';
cout << '\n';
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |