제출 #503580

#제출 시각아이디문제언어결과실행 시간메모리
503580fvogel499Harbingers (CEOI09_harbingers)C++14
0 / 100
230 ms28344 KiB
/* * File created on 01/08/2022 at 10:53:58. * Link to problem: * Description: * Time complexity: O() * Space complexity: O() * Status: --- * Copyright: Ⓒ 2022 Francois Vogel */ #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <functional> using namespace std; using namespace __gnu_pbds; #define pii pair<int, int> #define f first #define s second #define vi vector<int> #define all(x) x.begin(), x.end() #define size(x) (int)((x).size()) #define pb push_back #define ins insert #define cls clear #define int ll #define ll long long #define ld long double typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; const int siz = 1e5+40; const int inf = 1e18; vector<pii> graph [siz]; int height [siz]; int dp [siz]; int prep [siz]; int speed [siz]; map<ld, int> opt; vi q; ld xIntercept(int a1, int b1, int a2, int b2) { if (a1-a2 == 0) return (ld)(b2-b1)*(ld)(inf); return (ld)(b2-b1)/(ld)(a1-a2); } void dfs(int x, int p = -1) { if (p == -1) dp[x] = 0; else { auto it = opt.upper_bound(speed[x]); it = prev(it); dp[x] = -height[(*it).s]*speed[x]+dp[(*it).s]; dp[x] += height[x]*speed[x]+prep[x]; } vector<pair<ld, int>> rem; // while (size(q) >= 2 && xIntercept(-height[q.back()], dp[q.back()], -height[q[size(q)-2]], dp[q[size(q)-2]]) >= xIntercept(-height[x], dp[x], -height[q.back()], dp[q.back()])) { // rem.pb(*(prev(opt.end()))); // opt.erase(prev(opt.end())); // q.pop_back(); // } // reverse(all(rem)); // first in rem is now deepest in stack q ld fromX = -inf; if (!q.empty()) { fromX = ceil(xIntercept(-height[x], dp[x], -height[q.back()], dp[q.back()])); } opt[fromX] = x; q.pb(x); for (pii y : graph[x]) if (y.f != p) { height[y.f] = height[x]+y.s; dfs(y.f, x); } q.pop_back(); // opt.erase(prev(opt.end())); // for (pair<ld, int> i : rem) { // q.pb(i.s); // opt[i.f] = i.s; // } } signed main() { cin.tie(0); ios_base::sync_with_stdio(0); int n; cin >> n; for (int i = 0; i < n-1; i++) { int na, nb, lw; cin >> na >> nb >> lw; na--; nb--; graph[na].pb(pii(nb, lw)); graph[nb].pb(pii(na, lw)); } for (int i = 1; i < n; i++) cin >> prep[i] >> speed[i]; dfs(0); for (int i = 1; i < n; i++) cout << dp[i] << ' '; cout.flush(); int d = 0; d++; }
#Verdict Execution timeMemoryGrader output
Fetching results...