# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
130798 | 2019-07-16T05:44:57 Z | 송준혁(#3172) | Harbingers (CEOI09_harbingers) | C++14 | 168 ms | 26844 KB |
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL, LL> pii; int N; vector<pii> adj[101010]; int P[101010]; LL A[101010], B[101010], ans[101010]; LL D[101010]; struct CHT{ vector<pii> L; void push(pii l){ int t = L.size()-1; while(t > 0 && (L[t].second-l.second)*(L[t].first-L[t-1].first) < (L[t-1].second-L[t].second)*(l.first-L[t].first)) L.pop_back(), t--; L.push_back(l); } LL read(LL x){ if (L.size() == 1) return 0; int l=1, r=L.size()-1, ret=0; while (l <= r){ int mid = (l+r)/2; if (L[mid-1].second-L[mid].second < x*(L[mid].first-L[mid-1].first)) ret=mid, l = mid+1; else r = mid-1; } return L[ret].first * x + L[ret].second; } } CH; void dfs(int u, int p, LL d){ for (pii v : adj[u]){ if (v.first == p) continue; if (u == 1){ CH.L.clear(); CH.L.push_back(pii(0, 0)); } ans[v.first] = A[v.first]*(d+v.second) + B[v.first] - CH.read(A[v.first]); CH.push(pii(d+v.second, -ans[v.first])); dfs(v.first, u, d+v.second); } } void dfs2(int u, int p){ ans[u] = 1234567890123456ll, P[u] = p; for (int a=p; a!=0; a=P[a]) ans[u] = min(ans[u], A[u]*(D[u]-D[a]) + B[u] + ans[a]); if (u == 1) ans[u] = 0; for (pii v : adj[u]){ if (v.first == p) continue; D[v.first] = D[u] + v.second; dfs2(v.first, u); } } int main(){ scanf("%d", &N); for (int i=1; i<N; i++){ int u, v, w; scanf("%d %d %d", &u, &v, &w); adj[u].push_back(pii(v, w)); adj[v].push_back(pii(u, w)); } for (int i=2; i<=N; i++) scanf("%lld %lld", &B[i], &A[i]); if (N > 3000) dfs(1, 0, 0); else dfs2(1, 0); for (int i=2; i<=N; i++) printf("%lld ", ans[i]); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2680 KB | Output is correct |
2 | Correct | 17 ms | 3064 KB | Output is correct |
3 | Correct | 69 ms | 12856 KB | Output is correct |
4 | Correct | 98 ms | 17868 KB | Output is correct |
5 | Correct | 128 ms | 22092 KB | Output is correct |
6 | Correct | 164 ms | 26844 KB | Output is correct |
7 | Incorrect | 89 ms | 12920 KB | Output isn't correct |
8 | Incorrect | 168 ms | 18412 KB | Output isn't correct |
9 | Incorrect | 151 ms | 21068 KB | Output isn't correct |
10 | Incorrect | 139 ms | 19668 KB | Output isn't correct |