제출 #319116

#제출 시각아이디문제언어결과실행 시간메모리
319116thecodingwizardHarbingers (CEOI09_harbingers)C++11
70 / 100
1101 ms27748 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define ii pair<int, int> #define f first #define s second #define pb push_back #define mp make_pair #define all(x) x.begin(), x.end() #define F0R(i, n) for (int i = 0; i < n; i++) #define FOR(i, a, b) for (int i = a; i < b; i++) #define inf 1000000010 #define maxn 100000 int n; vector<ii> adj[maxn]; ll dp[maxn]; ll d[maxn]; ii A[maxn]; void dfsd(int u, int p, ll di = 0) { d[u] = di; for (auto v : adj[u]) { if (v.f != p) dfsd(v.f, u, di+v.s); } } struct Func { ll m, b; long double intersectX(Func other) { return (long double)(other.b-b)/(m-other.m); } ll eval(ll x) { return m*x+b; } }; deque<Func> dq; vector<int> nums; auto cmp = [](int idx, int x) { return dq[idx].intersectX(dq[idx+1]) < x; }; void dfs(int u, int p) { if (u == 0) { dp[u] = 0; } else { int idx = *lower_bound(nums.begin(), nums.begin() + dq.size()-1, A[u].s, cmp); ll v = dq[idx].eval(A[u].s); dp[u] = A[u].f + (ll)A[u].s*d[u] + v; } Func f = {-d[u], dp[u]}; vector<Func> removed; while (dq.size() >= 2 && dq[dq.size()-1].intersectX(dq[dq.size()-2]) >= dq[dq.size()-2].intersectX(f)) { removed.pb(dq.back()); dq.pop_back(); } dq.pb(f); for (auto v : adj[u]) { if (v.f != p) dfs(v.f, u); } dq.pop_back(); for (int i = removed.size()-1; ~i; i--) dq.pb(removed[i]); } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n; F0R(i, n-1) { int u, v, d; cin >> u >> v >> d; --u; --v; adj[u].pb(mp(v, d)); adj[v].pb(mp(u, d)); } F0R(i, n-1) { int a, b; cin >> a >> b; A[i+1] = mp(a, b); } dfsd(0, 0); nums = vector<int>(n); for (int i = 0; i < n; i++) nums[i] = i; dfs(0, 0); FOR(i, 1, n) { cout << dp[i] << " \n"[i == n-1]; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...