제출 #1124648

#제출 시각아이디문제언어결과실행 시간메모리
1124648Marko2604Harbingers (CEOI09_harbingers)C++17
90 / 100
161 ms32992 KiB
#include<bits/stdc++.h> #define ll long long #define MAXN 100003 using namespace std; vector<vector<pair<int,int>>>T(MAXN); int s[MAXN], v[MAXN]; struct line { int node; ll k,n; }; ll eval(ll x, line *l) { return l->k*x+l->n; } ll depth[MAXN]; void depth_dfs(int node, int p) { for(auto i:T[node]) { if(i.first!=p) { depth[i.first]=(ll)i.second+depth[node]; depth_dfs(i.first, node); } } } vector<vector<line*>>lichao(262151); vector<vector<int>>loc(MAXN); vector<int>xx; int sz; void make_lichao(int n) { sz = (1<<((int)ceil(log2(n)))); for(int i=1;i<=n;i++) xx.push_back(v[i]); while(xx.size()<sz) xx.push_back(0); sort(xx.begin(),xx.end()); } void add_line(line *ln, int node, int l, int r) { if(lichao[node].empty()) { lichao[node].push_back(ln); loc[ln->node].push_back(node); return; } line *lo = lichao[node].back(); ll lold = eval(xx[l], lo), rold = eval(xx[r], lo); ll lnew = eval(xx[l], ln), rnew = eval(xx[r], ln); if(lnew>=lold && rnew>=rold) return; if(lnew<=lold && rnew<=rold) { lichao[node].push_back(ln); loc[ln->node].push_back(node); return; } int mid = (l+r)/2; ll mold = eval(xx[mid], lo), mnew = eval(xx[mid], ln); if(lnew<=lold) { if(mnew<=mold) { lichao[node].push_back(ln); loc[ln->node].push_back(node); add_line(lo, 2*node+1, mid+1, r); return; } else { add_line(ln, 2*node, l, mid); return; } } else { if(mnew<=mold) { lichao[node].push_back(ln); loc[ln->node].push_back(node); add_line(lo, 2*node, l, mid); return; } else { add_line(ln, 2*node+1, mid+1, r); return; } } return; } void pop_line(int node) { while(!loc[node].empty()) { lichao[loc[node].back()].pop_back(); loc[node].pop_back(); } return; } ll get_val(int x) { ll res = 100000000000000000; int l=0, r=sz-1, node=1; while(l<=r) { if(!lichao[node].empty()) res=min(res, eval(x, lichao[node].back())); int mid=(l+r)/2; if(xx[mid]<=x) { l=mid+1; node=node*2+1; } else { r=mid-1; node=node*2; } } return res; } ll dp[MAXN]; void dp_dfs(int node, int p) { if(node != 1 ) dp[node]=(ll)(s[node])+(ll)(v[node])*depth[node]+get_val(v[node]); line l; l.node=node; l.k=-depth[node]; l.n=dp[node]; add_line(&l, 1, 0, sz-1); for(auto i:T[node]) { if(i.first!=p) { dp_dfs(i.first,node); } } pop_line(l.node); } int main() { ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); int n; cin>>n; for(int i=1;i<n;i++) { int u1,v1; ll w; cin>>u1>>v1>>w; T[u1].emplace_back(v1,w); T[v1].emplace_back(u1,w); } s[1]=0, v[1]=0; for(int i=2;i<=n;i++) cin>>s[i]>>v[i]; depth[1]=0; depth_dfs(1,1); make_lichao(n); dp[1]=0; dp_dfs(1,1); for(int i=2;i<=n;i++) cout<<dp[i]<<" "; cout<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...