@OceanEye7年前
04/17
08:26
题面大概是这样子的:
很裸,就学了一下可并堆的姿势然后就写了
1A啊:-D
写的是左偏树,安利百度文库的文章
但是不知道为什么跑了3k+ms
不理了可能是vector的原因吧
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include <cstdio> #include <algorithm> #include <vector> #define p(x) ('0'<=x&&x<='9') #define ll long long char cc; template <class T> void read( T &x ) { x=0; cc=getchar(); while(!p(cc)) cc=getchar(); while(p(cc)) { x=x*10+cc-48; cc=getchar(); } } template <class T,class TT> void read(TT &_,T &__,T &___) { read(_); read(__); read(___); } template <class T> void comp( T &x, T y ) { x>y?x=x:x=y; } using namespace std; #define N 100010 // zuo pian shu struct node { int l,r,k,d; }pool[N]; int combine(int _,int __) { if(!~_) return __; if(!~__) return _; if(pool[_].k<pool[__].k) swap(_,__); pool[_].r=combine(pool[_].r,__); if(~pool[_].r) pool[_].d=pool[pool[_].r].d+1; else pool[_].d=0; return _; } void pop(int &_) { int l=pool[_].l,r=pool[_].r; _=combine(l,r); } // vector <int> G[N]; ll C[N],L[N],ANS,SUM[N]; int n,m,SIZ[N],rt[N]; void init() { read(n); read(m); for(int i=1,_;i<=n;i++) { G[i].reserve(10); read(_,C[i],L[i]); G[_].push_back(i); } } void dfs(int x) { pool[x].l=pool[x].r=-1; SUM[x]=pool[x].k=C[x]; SIZ[x]=1; rt[x]=x; for(int i=0,to;i<G[x].size();i++) { to=G[x][i]; dfs(G[x][i]); rt[x]=combine(rt[x],rt[to]); SUM[x]+=SUM[to]; SIZ[x]+=SIZ[to]; } for(;SUM[x]>m;) { SUM[x]-=pool[rt[x]].k; pop(rt[x]); SIZ[x]--; } comp(ANS,L[x]*SIZ[x]); } int main() { init(); dfs(1); printf("%lld",ANS); return 0; } |