제출 #491487

#제출 시각아이디문제언어결과실행 시간메모리
491487blueHarbingers (CEOI09_harbingers)C++17
0 / 100
162 ms26524 KiB
#include <iostream> #include <vector> #include <cassert> using namespace std; using vi = vector<int>; using ll = long long; using vll = vector<ll>; #define pb push_back const int maxN = 100'000; const int lgN = 17; ll INF = 2'000'000'001; vector<pair<int, ll>> edge[1+maxN]; vll S(1+maxN), V(1+maxN); vi P(1+maxN); vll D(1+maxN, 0); vi ord; void dfs(int u, int p) { ord.push_back(u); P[u] = p; for(auto x: edge[u]) { int v = x.first; ll d = x.second; if(v == p) continue; D[v] = D[u] + d; dfs(v, u); } } struct line { ll a; ll b; ll eval(ll x) { return a*x + b; } }; bool intersect_comp(line A, line B, line C, line D) { //A.a * x + A.b == B.a * x + B.b, x = (B.b - A.b)/(A.a - B.a) ll mul = 1; if(A.a - B.a < 0) mul *= -1; if(C.a - D.a < 0) mul *= -1; return mul * (B.b - A.b) * (C.a - D.a) < mul * (D.b - C.b) * (A.a - B.a); } vector<line> cht(1+maxN); int cht_anc[1+maxN][1+lgN]; void insert_line(int u, line l) { cht[u] = l; int a = cht_anc[u][0]; for(int e = lgN; e >= 0; e--) { int v = cht_anc[a][e]; if(v == 1) continue; int w = cht_anc[v][0]; if(!intersect_comp(cht[w], cht[v], cht[v], l)) a = w; } cht_anc[u][0] = a; for(int e = 1; e <= lgN; e++) cht_anc[u][e] = cht_anc[ cht_anc[u][e-1] ][e-1]; } ll query(int u, ll x) { for(int e = lgN; e >= 0; e--) { int v = cht_anc[u][e]; if(v == 1) continue; int w = cht_anc[v][0]; ll mul = 1; if(cht[w].a - cht[v].a < 0) mul = -1; if(x * (cht[w].a - cht[v].a) * mul <= (cht[v].b - cht[w].b) * mul) u = w; } return cht[u].eval(x); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N; cin >> N; for(int i = 1; i <= N-1; i++) { int u, v; ll d; cin >> u >> v >> d; edge[u].pb({v, d}); edge[v].pb({u, d}); } for(int i = 2; i <= N; i++) cin >> S[i] >> V[i]; dfs(1, 1); for(int i = 1; i <= N; i++) for(int e = 0; e <= lgN; e++) cht_anc[i][e] = i; insert_line(1, {0, 0}); vll dp(1+N, INF); dp[1] = 0; for(int u: ord) { if(u == 1) continue; dp[u] = ll(S[u]) + ll(V[u])*ll(D[u]) + query(P[u], V[u]); insert_line(u, {-D[u], dp[u]}); } for(int i = 2; i <= N; i++) cout << dp[i] << ' '; cout << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...