BZOJ 2500 幸福的道路(race) 树上直径+平衡树

structHeal

{

    priority_queue<int> real;

    priority_queue<int> stack;

    void push(int x){

        real.push(x);

    }

    void pop(int x){

        stack.push(x);

    }

    int top(){

        while(real.empty()==&&stack.empty()==&&real.top()==stack.top())

         real.pop(),stack.pop();

        if(real.empty())return0;

        return real.top();

    }

}

这样打堆虽然方便但是top到最后大约有6，7的常数。

今天考试卡常卡的怀疑人生……..这个故事告诉我们千万不要忘了常数分析..........

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#include<ctime>

#include<iostream>

#define MAXN 1000010

using namespace std;

inline int read()

{

    int sum=;

    char ch=getchar();

    while(ch<''||ch>'')ch=getchar();

    while(ch>=''&&ch<='')

    {

        sum=(sum<<)+(sum<<)+ch-'';

        ch=getchar();

    }

    return sum;

}

struct ScapeGoat_Tree

{

    struct node

    {

       node *ch[];

       int key,size,cover,ex;

       void update()

       {

         size=ch[]->size+ch[]->size+ex;

         cover=ch[]->cover+ch[]->cover+;

       }

       bool bad()

       {

         return ch[]->cover>=cover*0.756+||ch[]->cover>=cover*0.756+;

       }

    }Mem[MAXN],*null,*root,*stack[MAXN],*lst[MAXN];

    int len,top;

    void Init()

    {

       root=null=Mem;

       null->size=null->cover=null->ex=;

       null->ch[]=null->ch[]=Mem;

       for(int i=;i<MAXN;i++)stack[++top]=Mem+i;

    }

    node *New(int key)

    {

       node *t=stack[top--];

       t->ch[]=t->ch[]=null;

       t->size=t->cover=t->ex=;

       t->key=key;

       return t;

    }

    void travel(node *p)

    {

       if(p==null)return;

       travel(p->ch[]);

       if(p->ex)lst[++len]=p;

       else stack[++top]=p;

       travel(p->ch[]);

    }

    node *divide(int l,int r)

    {

        if(l>r)return null;

        int mid=(l+r)>>;

        lst[mid]->ch[]=divide(l,mid-);

        lst[mid]->ch[]=divide(mid+,r);

        lst[mid]->update();

        return lst[mid];

    }

    void rebuild(node *&p)

    {

        len=;

        travel(p);

        p=divide(,len);

    }

    node **insert(node *&p,int key)

    {

        if(p==null)

        {

            p=New(key);

            return &null;

        }

        p->size++;

        p->cover++;

        node **ret=insert(p->ch[p->key<=key],key);

        if(p->bad())ret=&p;

        return ret;

    }

    void erace(node *p,int k)

    {

        p->size--;

        if(p->ex&&k==p->ch[]->size+)

        {

            p->ex=;

            return;

        }

        if(k<=p->ch[]->size)erace(p->ch[],k);

        else erace(p->ch[],k-p->ch[]->size-p->ex);

    }

    int Kth(int k)

    {

        node *p=root;

        while(p!=null)

        {

            if(p->ex&&k==p->ch[]->size+)return p->key;

            else if(p->ch[]->size>=k)p=p->ch[];

            else k-=p->ch[]->size+p->ex,p=p->ch[];

        }

    }

    int Rank(int x)

    {

        node *p=root;

        int ret=;

        while(p!=null)

        if(p->key>=x)

            p=p->ch[];

        else

            ret+=p->ch[]->size+p->ex,p=p->ch[];

        return ret;

    }

    void Insert(int x)

    {

        node **p=insert(root,x);

        if(*p!=null)rebuild(*p);

    }

    void Erace_kth(int k)

    {

        erace(root,k);

        if(root->size<root->cover*0.756)rebuild(root);

    }

    void Erace(int x)

    {

        Erace_kth(Rank(x));

    }

}YY;

inline int Max(int x,int y)

{

    return x>y?x:y;

}

inline int Abs(int x)

{

    return x<?-x:x;

}

int n,m;

struct Tr

{

    int to,next,w;

}c[MAXN<<];

int head[MAXN],t;

int f[MAXN];

inline void add(int x,int y,int z)

{

    c[++t].to=y;

    c[t].w=z;

    c[t].next=head[x];

    head[x]=t;

}

int A[MAXN];

bool mark[MAXN];

int q[MAXN],top,tail,one,two;

inline void bfs1()

{

    memset(mark,,sizeof(mark));

    memset(A,,sizeof(A));

    q[]=;

    top=tail=;

    int now=;

    one=;

    mark[]=;

    while(top<=tail)

    {

        int x=q[top++];

        if(A[x]>now)

        {

            one=x;

            now=A[x];

        }

        for(int i=head[x];i;i=c[i].next)

        if(mark[c[i].to]==)

        {

            mark[c[i].to]=;

            q[++tail]=c[i].to;

            A[c[i].to]=A[x]+c[i].w;

        }

    }

}

inline void bfs2()

{

    memset(mark,,sizeof(mark));

    memset(A,,sizeof(A));

    q[]=one;

    top=tail=;

    int now=;

    two=one;

    mark[one]=;

    while(top<=tail)

    {

        int x=q[top++];

        if(A[x]>now)

        {

            two=x;

            now=A[x];

        }

        for(int i=head[x];i;i=c[i].next)

        if(mark[c[i].to]==)

        {

            mark[c[i].to]=;

            q[++tail]=c[i].to;

            A[c[i].to]=A[x]+c[i].w;

        }

    }

}

inline void bfs3()

{

    memset(mark,,sizeof(mark));

    memset(A,,sizeof(A));

    q[]=one;

    top=tail=;

    mark[one]=;

    while(top<=tail)

    {

        int x=q[top++];

        for(int i=head[x];i;i=c[i].next)

        if(mark[c[i].to]==)

        {

            mark[c[i].to]=;

            q[++tail]=c[i].to;

            A[c[i].to]=A[x]+c[i].w;

        }

    }

}

int B[MAXN];

inline void bfs4()

{

    memset(mark,,sizeof(mark));

    q[]=two;

    top=tail=;

    mark[two]=;

    while(top<=tail)

    {

        int x=q[top++];

        for(int i=head[x];i;i=c[i].next)

        if(mark[c[i].to]==)

        {

            mark[c[i].to]=;

            q[++tail]=c[i].to;

            B[c[i].to]=B[x]+c[i].w;

        }

    }

}

inline void Init()

{

    n=read(),m=read();

    m=Abs(m);

    YY.Init();

    for(int i=;i<=n;i++)

    {

        int x=read(),y=read();

        add(x,i,y);

        add(i,x,y);

    }

    bfs1(),bfs2(),bfs3(),bfs4();

    for(int i=;i<=n;i++)A[i]=Max(A[i],B[i]);

}

inline bool jud(int p)

{

    int x=YY.Kth(),y=YY.Kth(YY.root->size);

    if(Abs(x-p)>m||Abs(y-p)>m)return ;

    return ;

}

inline void work()

{

    top=;

    int ans=;

    YY.Insert(A[]);

    for(int i=;i<=n;i++)

    {

        while(top!=i&&!jud(A[i]))

         YY.Erace(A[top]),top++;

        YY.Insert(A[i]);

        ans=Max(ans,YY.root->size);

    }

    printf("%d",ans);

}

int main()

{

    //freopen("race.in","r",stdin);

    //freopen("race.out","w",stdout);

    Init();

    work();

    return ;

}

巴特西

BZOJ 2500 幸福的道路(race) 树上直径+平衡树

最新文章

热门文章