# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
935858 | Blagoj | Harbingers (CEOI09_harbingers) | C++17 | 128 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;
#define endl '\n'
#define ll long long
#define all(x) (x).begin(), (x).end()
const int mxn = 1e5 + 10;
vector<pair<ll, ll>> g[mxn];
struct Line {
ll m = 0, b = -1e14;
int l, r, lp = -1, rp = -1;
};
void swap(Line &a, Line &b) {
swap(a.m, b.m);
swap(a.b, b.b);
}
ll f(Line a, ll x) {
return a.m * x + a.b;
}
stack<pair<ll, Line>> s;
struct LiChao {
int cnt = 1;
vector<Line> sgt;
LiChao() {
sgt.resize(2e5);
sgt[1].l = 1;
sgt[1].r = 1e9;
}
void update(int k, Line nw) {
int l = sgt[k].l, r = sgt[k].r, mid = (l + r) / 2;
if (f(nw, l) <= f(sgt[k], l) && f(nw, r) <= f(sgt[k], r)) return;
if (f(nw, l) >= f(sgt[k], l) && f(nw, r) >= f(sgt[k], r)) {
s.push({k, sgt[k]});
swap(sgt[k], nw);
return;
}
bool f1 = f(nw, l) > f(sgt[k], l);
bool f2 = f(nw, mid) > f(sgt[k], mid);
if (f2) {
s.push({k, sgt[k]});
swap(sgt[k], nw);
}
if (l == r) return;
if (f1 != f2) {
if (sgt[k].lp == -1) {
sgt[k].lp = ++cnt;
sgt[cnt].l = l;
sgt[cnt].r = mid;
}
update(sgt[k].lp, nw);
}
else {
if (sgt[k].rp == -1) {
sgt[k].rp = ++cnt;
sgt[cnt].l = mid + 1;
sgt[cnt].r = r;
}
update(sgt[k].rp, nw);
}
}
ll get(int k, ll x) {
int l = sgt[k].l, r = sgt[k].r, mid = (l + r) / 2;
ll ans = f(sgt[k], x);
if (x <= mid) {
if (sgt[k].lp != -1) ans = max(ans, get(sgt[k].lp, x));
}
else if (sgt[k].rp != -1) ans = max(ans, get(sgt[k].rp, x));
return ans;
}
void rollback(int x) {
while (s.size() > x) {
swap(sgt[s.top().first], s.top().second);
s.pop();
}
}
} lc;
ll dist[mxn], ans[mxn], start[mxn], speed[mxn];
void dfs(int cur = 1, int par = -1) {
int sz = s.size();
if (cur != 1) {
ans[cur] = -lc.get(1, speed[cur]) + start[cur] + speed[cur] * dist[cur];
lc.update(1, {dist[cur], -ans[cur]});
}
for (auto x : g[cur]) {
if (x.first != par) {
dist[x.first] = dist[cur] + x.second;
dfs(x.first, cur);
}
}
lc.rollback(sz);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
lc.update(1, {0, 0});
int n;
cin >> n;
for (int i = 0; i < n - 1; i++) {
int f, t, w;
cin >> f >> t >> w;
g[f].push_back({t, w});
g[t].push_back({f, w});
}
for (int i = 2; i <= n; i++) cin >> start[i] >> speed[i];
dfs();
for (int i = 2; i <= n; i++) cout << ans[i] << " ";
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |