제출 #373418

#제출 시각아이디문제언어결과실행 시간메모리
373418arujbansalHarbingers (CEOI09_harbingers)C++17
10 / 100
193 ms65540 KiB
#include <iostream> #include <algorithm> #include <vector> #include <map> #include <set> #include <array> #include <stack> #include <queue> #include <random> #include <numeric> #include <functional> #include <chrono> #include <utility> #include <iomanip> #include <assert.h> using namespace std; void dbg_out() { cerr << endl; } template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); } #define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__) #define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #define rng_seed(x) mt19937 rng(x) #define all(x) (x).begin(), (x).end() #define sz(x) (int) (x).size() #define int long long const int MXN = 1e5 + 5, INF = 1e17; vector<pair<int, int>> g[MXN]; int S[MXN], V[MXN], version[MXN], ans[MXN]; int last_version; struct Line { int m, c; Line() { m = 0; c = INF; } Line(int m, int c) : m(m), c(c) {} int val(int x) { return m * x + c; } }; struct Node { Line line; Node *lc, *rc; Node() : lc(0), rc(0) {} }; deque<Node> buffer; deque<Node*> root; Node* new_node() { buffer.emplace_back(); return &buffer.back(); } void modify(Node* &prev, Node* &cur, int l, int r, Line new_line) { if (!prev) { cur->line = new_line; return; } cur->line = prev->line; if (r - l <= 1) return; cur->lc = prev->lc; cur->rc = prev->rc; int mid = l + (r - l) / 2; if (new_line.val(mid) < cur->line.val(mid)) swap(cur->line, new_line); if (new_line.val(l) < cur->line.val(l)) { cur->lc = new_node(); modify(prev->lc, cur->lc, l, mid, new_line); } else { cur->rc = new_node(); modify(prev->rc, cur->rc, mid + 1, r, new_line); } } int query(Node* &cur, int l, int r, int x) { if (!cur) return INF; int res = cur->line.val(x); if (r - l <= 1) return res; int mid = l + (r - l) / 2; if (x <= mid) return min(res, query(cur->lc, l, mid, x)); else return min(res, query(cur->rc, mid + 1, r, x)); } void modify(int modify_version, int m, int c) { root.emplace_back(new_node()); modify(root[modify_version], root[last_version], 0, 1000000000, Line(m, c)); } int query(int qry_version, int x) { return query(root[qry_version], 0, 1000000000, x); } void dfs(int u, int p, int dist) { version[u] = ++last_version; ans[u] = min(dist * V[u] + S[u], query(version[p], V[u]) + dist * V[u] + S[u]); modify(version[p], -dist, ans[u]); for (const auto &[v, d] : g[u]) { if (v == p) continue; dfs(v, u, dist + d); } } void solve() { int N; cin >> N; for (int i = 0; i < N - 1; i++) { int u, v, d; cin >> u >> v >> d; g[u].emplace_back(v, d); g[v].emplace_back(u, d); } for (int i = 2; i <= N; i++) cin >> S[i] >> V[i]; root.emplace_back(new_node()); version[1] = 0; for (const auto &[v, d] : g[1]) { dfs(v, 1, d); } for (int i = 2; i <= N; i++) cout << ans[i] << " "; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int TC = 1; // cin >> TC; while (TC--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...