# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
883158 | anarch_y | Harbingers (CEOI09_harbingers) | C++17 | 96 ms | 65536 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 int inf = 1e9;
struct line{
int m, c;
double p;
int eval(int x){
return m*x+c;
}
};
struct CHT{
vector<line> hull; int id;
CHT() { id = 0;}
double getx(int m1, int c1, int m2, int c2){
if(m1==m2) return inf;
else return (double)(c1-c2)/(double)(m2-m1);
}
void addline(int m, int c){
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});
}
int best(int 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);
}
int fast(int x){
while(id+1<(int)hull.size() and hull[id+1].p <= x) id++;
return hull[id].eval(x);
}
};
vector<pii> adj[100001];
int 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] + 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] = 0; dp[1] = 0;
cht[1].addline(0, 0);
dfs(1, 0);
for(int i=2; i<=N; i++) cout << dp[i] << ' ';
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |