Submission #883066

#TimeUsernameProblemLanguageResultExecution timeMemory
883066nghiaaaHarbingers (CEOI09_harbingers)C++14
0 / 100
153 ms55204 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define db double #define ii pair<int,int> #define f first #define s second #define mp make_pair #define mt make_tuple #define pb push_back #define all(v) v.begin(),v.end() #define BIT(i) ((ll)1<<(i)) #define endl "\n" #define debug(x) for (auto p: x) cout<<p<<' ';cout<<endl #define forw(i,j,z) for(int i=(int)j;i<=(int)z;i++) #define forw2(i,j,z,k) for(int i=(int)j;i<=(int)z;i+=k) #define ford(i,j,z) for (int i=(int)j;i>=(int)z;i--) #define ford2(i,j,z,k) for (int i=(int)j;i>=(int)z;i-=k) #define sz(a) (int)a.size() const ll inf=LLONG_MAX; const int N=1e5; struct Line{ mutable ll a,b; mutable ll pos; Line(ll a1,ll b1):a(a1),b(b1),pos(0){} bool operator < (const Line &u) const{ return a<u.a; } bool operator < (const ll &p) const { return pos<p; } }; int timeDFS=0; vector<pair<bool,Line> > changes[N+1]; struct LineContainer: multiset<Line,less<> > { ll div(ll u,ll v) { return u/v - ((u^v)<0&&(u%v)); } bool isect(iterator x,iterator y) { changes[timeDFS].push_back(mp(1,*x)); if (y==end()){ x->pos=inf; changes[timeDFS].push_back(mp(0,*x)); return 0; } if (x->a==y->a) x->pos= x->b > y->b ? inf: -inf; else x->pos= div(x->b - y->b,y->a - x->a); changes[timeDFS].push_back(mp(0,*x)); return x->pos>=y->pos; } void add(Line v) { iterator z=insert(v),y=z++,x=y; changes[timeDFS].push_back(mp(0,v)); while(isect(y,z)){ changes[timeDFS].push_back(mp(1,*z)); z=erase(z); } while((y=x)!=begin()&&isect(--x,y)){ changes[timeDFS].push_back(mp(1,*y)); isect(x,erase(y)); } } ll query(ll u) { Line d=*lower_bound(u); return d.a*u + d.b; } } haha; int n; vector<ii> adj[N+1]; ll dp[N+1],h[N+1]; int prepare[N+1],velocity[N+1]; void dfs(int u,int dad) { int now=++timeDFS; if (u>1){ dp[u]=-haha.query(velocity[u])+h[u]*velocity[u]+prepare[u]; haha.add(Line(h[u],-(dp[u]))); } forw(i,0,sz(adj[u])-1) if (adj[u][i].f!=dad) { int v=adj[u][i].f,d=adj[u][i].s; h[v]=h[u]+d; dfs(v,u); } if (u>1){ ford(i,sz(changes[now])-1,0) { if (changes[now][i].f==0) haha.erase(haha.find(changes[now][i].s)); else haha.insert(changes[now][i].s); } changes[now].clear(); } } void solve() { haha.add(Line(0,0)); cin>>n; forw(i,2,n) { int u,v,d; cin>>u>>v>>d; adj[u].push_back(mp(v,d)); adj[v].push_back(mp(u,d)); } forw(i,2,n) cin>>prepare[i]>>velocity[i]; dfs(1,1); forw(i,2,n) cout<<dp[i]<<' '; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); //cout<<setprecision(6)<<fixed; //time_t TIME_TU=clock(); int t=1; //cin>>t; while(t--) solve(); //time_t TIME_TV=clock(); //cerr<<(db)(TIME_TV-TIME_TU)/CLOCKS_PER_SEC<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...