# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
528223 | sidon | Harbingers (CEOI09_harbingers) | C++17 | 140 ms | 65540 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define i64 int64_t
#define sp << ' ' <<
#define nl << '\n'
using T = pair<int, i64>;
const i64 INF = 2e9;
const int Z = 1e5+1;
#define eval(X, Y) (i64(Y.first) * X + Y.second)
vector<pair<int, T>> rb;
int vals[1<<18];
T sU; int sV;
#define m ((l + r) / 2)
struct LiChaoTree {
T v[1<<18];
void insert(int u, int l, int r) {
if(eval(vals[m], sU) < eval(vals[m], v[u]))
rb.emplace_back(u, v[u]), swap(sU, v[u]);
if(r - l < 2) return;
sU.first > v[u].first ? insert(2*u+1, l, m) : insert(2*u+2, m, r);
}
void insert(T u, int lim) {
sU = u; insert(0, 0, lim);
}
i64 query(int u, int l, int r) {
if(r - l < 2) return eval(vals[sV], v[u]);
return min(eval(vals[sV], v[u]), sV < m ? query(2*u+1, l, m) : query(2*u+2, m, r));
}
i64 query(int x, int lim) {
sV = x;
return query(0, 0, lim);
}
} lt;
int N, S[Z];
i64 V[Z]; //dp
vector<array<int, 2>> g[Z];
int d;
void dfs(int u) {
size_t rbP = size(rb);
V[u] = lower_bound(vals, vals + N - 1, V[u]) - vals;
V[u] = u ? lt.query(V[u], N - 1) + i64(S[u]) + i64(vals[V[u]]) * i64(d) : i64();
lt.insert({-d, V[u]}, N-1);
for(auto &[v, w] : g[u]) {
for(auto i = begin(g[v]); ; ++i) {
if((*i)[0] == u) {
g[v].erase(i);
break;
}
}
d += w;
dfs(v);
d -= w;
}
while(size(rb) > rbP) {
lt.v[rb.back().first] = rb.back().second;
rb.pop_back();
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
cin >> N;
for(int i = 1; i < N; ++i) {
int u, v, w;
cin >> u >> v >> w;
--u, --v;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
for(int i = 1; i < N; ++i) {
cin >> S[i] >> V[i];
vals[i-1] = V[i];
}
sort(vals, vals + N - 1);
dfs(0);
for(int i = 1; i < N; ++i)
cout << V[i] << ' ';
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |