제출 #377294

#제출 시각아이디문제언어결과실행 시간메모리
377294jhwest2Harbingers (CEOI09_harbingers)C++14
0 / 100
156 ms25964 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #define va first #define vb second using namespace std; typedef long long lint; typedef pair<int, int> pint; typedef pair<lint, lint> plint; const int MAX = 1e5 + 10; int n, S[MAX], V[MAX], Dist[MAX]; lint Dp[MAX]; vector<pint> G[MAX]; struct CHT { plint V[MAX]; int P[20][MAX], pos, sz; void update(lint a, lint b) { for (int i = 19; i >= 0; i--) { if (P[1][P[i][pos]] == 0) continue; int c = P[i][pos], p = P[1][c]; if ((V[c].vb - V[p].vb) * (V[c].va - a) > (b - V[c].vb) * (V[p].va - V[c].va)) pos = c; } P[1][++sz] = pos; P[0][sz] = sz; pos = sz; V[pos] = {a , b}; for (int i = 2; i < 20; i++) P[i][pos] = P[1][P[i - 1][P[i - 1][pos]]]; } lint query(lint x) { int t = pos; for (int i = 19; i >= 0; i--) { if (P[1][P[i][t]] == 0) continue; int c = P[i][t], p = P[1][c]; if ((V[c].vb - V[p].vb) > (V[p].va - V[c].va) * x) t = p; } return V[t].va * x + V[t].vb; } } C; void dfs(int prv, int cur) { if (cur != 1) Dp[cur] = C.query(V[cur]) + (lint)V[cur] * Dist[cur] + S[cur]; C.update(-Dist[cur], Dp[cur]); for (auto nxt : G[cur]) { if (prv == nxt.vb) continue; Dist[nxt.vb] = Dist[cur] + nxt.va; dfs(cur, nxt.vb); } C.pos = C.P[1][C.pos]; } int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> n; for (int i = 1; i < n; i++) { int x, y, w; cin >> x >> y >> w; G[x].emplace_back(w, y); G[y].emplace_back(w, x); } for (int i = 2; i <= n; i++) cin >> S[i] >> V[i]; dfs(0, 1); for (int i = 2; i <= n; i++) cout << Dp[i] << ' '; }
#Verdict Execution timeMemoryGrader output
Fetching results...