# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
130793 | 2019-07-16T05:35:36 Z | 송준혁(#3172) | Harbingers (CEOI09_harbingers) | C++14 | 192 ms | 26840 KB |
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL, LL> pii; int N; vector<pii> adj[101010]; LL A[101010], B[101010], ans[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); } } 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]); dfs(1, 0, 0); for (int i=2; i<=N; i++) printf("%lld ", ans[i]); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 2680 KB | Output isn't correct |
2 | Correct | 7 ms | 3320 KB | Output is correct |
3 | Correct | 66 ms | 12792 KB | Output is correct |
4 | Correct | 96 ms | 17776 KB | Output is correct |
5 | Correct | 118 ms | 22008 KB | Output is correct |
6 | Correct | 150 ms | 26840 KB | Output is correct |
7 | Incorrect | 88 ms | 12908 KB | Output isn't correct |
8 | Incorrect | 192 ms | 18556 KB | Output isn't correct |
9 | Incorrect | 148 ms | 21068 KB | Output isn't correct |
10 | Incorrect | 146 ms | 19736 KB | Output isn't correct |