# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
963857 | 2024-04-15T20:14:34 Z | sheldon | Harbingers (CEOI09_harbingers) | C++14 | 1000 ms | 25612 KB |
#include <bits/stdc++.h> using namespace std; const int nax = 1e5 + 5; struct line { long long m, b; long long eval (long long x) { return x * m + b; } pair<long long, long long> intersect (line ln) { // m1 * x + b1 = m2 * x = b2 return {ln.b - b, m - ln.m}; } }; bool check (line x, line y, line z) { pair<long long, long long> p1 = x.intersect (y), p2 = y.intersect (z); return (__int128) p1.first * p2.second >= (__int128) p2.first * p1.second; } struct convex_hull { vector<line> st; void insert (line ln) { if (st.empty ()) { st.push_back (ln); return; } while (st.size () >= 2 && check (st[st.size () - 2], st.back (), ln)) { st.pop_back (); } st.push_back (ln); } long long query (long long x) { int l = 0, r = (int) st.size () - 2; long long ans = 2e18; while (l <= r) { int mid = (l + r) / 2; pair<long long, long long> p1 = st[mid].intersect (st[mid + 1]); if (p1.first < x * p1.second) { l = mid + 1; } else { r = mid - 1; } } return st[r + 1].eval (x); } }; long long start[nax], per_km[nax]; long long ans[nax]; vector<pair<int, int>> edges[nax]; convex_hull hull; void dfs (int u, int p, long long path) { if (u != 1) ans[u] = start[u] + path * per_km[u] + hull.query (per_km[u]); vector<line> deleted; line z {-path, ans[u]}; while (hull.st.size () >= 2 && check (hull.st[hull.st.size () - 2], hull.st.back (), z)) { deleted.push_back (hull.st.back ()); hull.st.pop_back (); } hull.st.push_back (z); for (auto &it: edges[u]) { int v = it.first, x = it.second; if (v != p) { dfs (v, u, path + x); } } hull.st.pop_back (); reverse (deleted.begin (), deleted.end ()); for (auto &it : deleted) { hull.st.push_back (it); } } void solve() { int n; cin >> n; for (int i = 0; i < n - 1; ++i) { int u, v, x; cin >> u >> v >> x; edges[u].push_back ({v, x}); edges[v].push_back ({u, x}); } for (int i = 2; i <= n; ++i) { cin >> start[i] >> per_km[i]; } dfs (1, 0, 0); for (int i = 2; i <= n; ++i) { cout << ans[i] << ' '; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); solve(); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4696 KB | Output is correct |
2 | Correct | 2 ms | 5212 KB | Output is correct |
3 | Correct | 33 ms | 13660 KB | Output is correct |
4 | Correct | 40 ms | 17428 KB | Output is correct |
5 | Correct | 51 ms | 21588 KB | Output is correct |
6 | Correct | 73 ms | 25612 KB | Output is correct |
7 | Correct | 37 ms | 13064 KB | Output is correct |
8 | Execution timed out | 1047 ms | 17760 KB | Time limit exceeded |
9 | Execution timed out | 1047 ms | 13964 KB | Time limit exceeded |
10 | Execution timed out | 1101 ms | 19268 KB | Time limit exceeded |