# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
883161 | anarch_y | Harbingers (CEOI09_harbingers) | C++17 | 93 ms | 65536 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(x) begin(x), end(x)
#define pb push_back
const ll inf = 1e18;
struct line{
ll m, c;
long double p;
ll eval(ll x){
return (ll)(m*x+c);
}
};
struct CHT{
vector<line> hull; int id;
CHT() {id = 0;}
double getx(ll m1, ll c1, ll m2, ll c2){
if(m1==m2) return inf;
else return (long double)(c1-c2)/(long double)(m2-m1);
}
void addline(int m, int c){
long double p = -inf;
while(!hull.empty()){
line last = hull.back();
p = getx(m, c, last.m, last.c);
if(p==inf){
if(c>last.c) return;
else hull.pop_back();
}
else if(p<last.p) hull.pop_back();
else break;
}
hull.pb((line){m, c, p});
}
ll best(ll x){
int k = 0;
int L = 0, R = hull.size()-1;
while(L<=R){
int mid = (L+R)/2;
if(hull[mid].p <= x){
k = mid; L = mid+1;
}
else R = mid-1;
}
return hull[k].eval(x);
}
ll fast(ll x){
while(id+1<(int)hull.size() and hull[id+1].p <= x) id++;
return hull[id].eval(x);
}
};
vector<pii> adj[100001];
ll dist[100001], dp[100001];
CHT cht[100001];
int S[100001], F[100001];
void dfs(int s, int e){
for(auto pr: adj[s]){
int u = pr.first;
if(u == e) continue;
dist[u] = dist[s] + pr.second;
CHT temp = cht[s];
dp[u] = temp.best(F[u]) + S[u] + (ll)(F[u]*dist[u]);
temp.addline(-dist[u], dp[u]);
cht[u] = temp;
dfs(u, s);
}
cht[s].hull.clear();
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N; cin >> N;
for(int i=0; i<N-1; i++){
int a, b, d; cin >> a >> b >> d;
adj[a].pb({b, d}); adj[b].pb({a, d});
}
for(int i=2; i<=N; i++){
cin >> S[i] >> F[i];
}
dist[1] = 0LL; dp[1] = 0LL;
cht[1].addline(0LL, 0LL);
dfs(1, 0);
for(int i=2; i<=N; i++) cout << dp[i] << ' ';
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |