# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
474516 | pure_mem | Harbingers (CEOI09_harbingers) | C++14 | 1094 ms | 65540 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define X first
#define Y second
#define ll long long
#define MP make_pair
using namespace std;
const int N = 1e5 + 123;
const ll INF = 1e18;
typedef pair<ll, ll> Line;
ll f(Line me, ll x) {
return me.X * x + me.Y;
}
int CHT[N], n, sz;
vector< pair<int, ll> > g[N];
ll dp[N], d[N], sp[N], sl[N];
Line cf[N];
ll get(ll x) {
int l = 1, r = sz - 1;
while(l <= r) {
int m = (l + r) / 2;
if(f(cf[CHT[m]], x) < f(cf[CHT[m + 1]], x))
r = m - 1;
else
l = m + 1;
}
return f(cf[CHT[r + 1]], x);
}
bool bad(int x, int y, int z) {
return (cf[x].Y - cf[y].Y) * 1.0 / (cf[y].X - cf[x].X) >= (cf[x].Y - cf[z].Y) * 1.0 / (cf[z].X - cf[x].X);
}
void dfs(int v, int pr) {
if(pr != -1) {
dp[v] = get(sp[v]) + sl[v] + sp[v] * d[v];
}
cf[v] = {-d[v], dp[v]};
stack<int> his;
while(sz > 1 && bad(CHT[sz - 1], CHT[sz], v))
his.push(CHT[sz--]);
CHT[++sz] = v;
for(pair<int, ll> to: g[v]) {
if(to.X == pr) continue;
d[to.X] = d[v] + to.Y, dfs(to.X, v);
}
sz--;
while(!his.empty())
CHT[++sz] = his.top(), his.pop();
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1, x, y, z;i < n;i++) {
cin >> x >> y >> z;
g[x].push_back({y, z});
g[y].push_back({x, z});
}
for(int i = 2;i <= n;i++)
cin >> sl[i] >> sp[i];
dfs(1, -1);
for(int i = 2;i <= n;i++)
cout << dp[i] << " ";
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |