제출 #131537

#제출 시각아이디문제언어결과실행 시간메모리
131537lycHarbingers (CEOI09_harbingers)C++14
70 / 100
1078 ms31076 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef pair<int, ii> iii; typedef pair<ii, int> ri3; #define mp make_pair #define pb push_back #define fi first #define sc second #define SZ(x) (int)(x).size() #define ALL(x) begin(x), end(x) #define REP(i, n) for (int i = 0; i < n; ++i) #define FOR(i, a, b) for (int i = a; i <= b; ++i) #define RFOR(i, a, b) for (int i = a; i >= b; --i) const int MAXN = 1e5+5; int N; vector<ii> al[MAXN]; int S[MAXN], V[MAXN]; int p[MAXN]; int d[MAXN]; ll r[MAXN]; struct Line { int m; ll b; }; const Line END = {(int)-2e9, (ll)-3e18}; struct Op { Line o, n; }; struct Hull { vector<Line> v; vector<Op> h; int add(Line l) { //cout << "ADD " << l.m << " " << l.b << endl; int idx = SZ(h); int s; while ((s = SZ(v)) > 2) { if (((ll)l.b-v[s-1].b)*((ll)v[s-2].m-v[s-1].m) <= (((ll)v[s-1].b-v[s-2].b)*((ll)v[s-1].m-l.m))) h.emplace_back((Op){ v[s-1], END }), v.pop_back(); else break; } h.emplace_back((Op){ END, l }); v.emplace_back(l); return idx; } ll query(int x) { //cout << "QUERY " << SZ(v) << ": "; //for (auto l : v) cout << "(" << l.m << "," << l.b << ") "; //cout << endl; int lo = 0, hi = SZ(v)-1; while (lo < hi) { int mid = (lo+hi)/2; bool ok = ((ll)x*((ll)v[mid].m-v[mid+1].m) <= (ll)v[mid+1].b-v[mid].b); if (ok) hi = mid; else lo = mid+1; } return (ll)v[hi].m*x + v[hi].b; } void undo(int idx) { //cout << "UNDO " << endl; while (SZ(h) > idx) { Op cur = h.back(); if (cur.o.m == END.m && cur.o.b == END.b) { v.pop_back(); }//cout << "\t\tPOP\n"; } else { v.push_back(cur.o); }//cout << "\t\tPUSH " << cur.o.m << " " << cur.o.b << '\n'; } h.pop_back(); } } } ch; void dfs(int u) { r[u] = (ll)S[u] + (ll)V[u]*d[u]; //cout << u << " " << p[u] << endl; //for (int v = p[u]; v != 0; v = p[v]) r[u] = min(r[u], (ll)S[u] + (ll)V[u]*(d[u]-d[v]) + r[v]); if (u > 1) r[u] = min(r[u], ch.query(V[u]) + (ll)S[u] + (ll)V[u]*d[u]); int idx = ch.add({ -d[u], r[u] }); for (auto v : al[u]) if (v.fi != p[u]) { d[v.fi] = d[u] + v.sc; p[v.fi] = u; dfs(v.fi); } ch.undo( idx ); } int main() { //freopen("in.txt", "r", stdin); ios::sync_with_stdio(false); cin.tie(0); cin >> N; FOR(i,1,N-1){ int u, v, d; cin >> u >> v >> d; al[u].emplace_back(v, d); al[v].emplace_back(u, d); } FOR(i,2,N){ cin >> S[i] >> V[i]; } dfs(1); FOR(i,2,N) cout << r[i] << (i == N ? '\n' : ' '); }
#Verdict Execution timeMemoryGrader output
Fetching results...