CF1019E Raining season

https://www.luogu.org/problemnew/show/CF1019E
题解

\[dis=day*a+b
\]
\[b=-day*a+dis
\]
然后就变成了斜率优化。
考虑边分治，每次把两边的凸包求出来。
然后再把两边的凸包做闵可夫斯基和求出新的凸包。
最后把分治求的的所有凸包上的点再做一次凸包即可得到答案凸包。
代码

#include<bits/stdc++.h>

#define N 200007

#define M 1000009

using namespace std;

typedef long long ll;

int head[N],tot=1,dp[N],sum,size[N],root,rootval,_rootval,top,n,m,num,cuu[2];

bool vis[N],jin[N<<1];

ll ans[M];

inline ll rd(){

  ll x=0;char c=getchar();bool f=0;

  while(!isdigit(c)){if(c=='-')f=1;c=getchar();}

  while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

  return f?-x:x;

}

struct point{

    double x,y;

    inline point operator +(const point &b)const{return point{x+b.x,y+b.y};}

    inline point operator -(const point &b)const{return point{x-b.x,y-b.y};}

    inline double operator *(const point &b)const{return x*b.y-y*b.x;}

}cu[2][N],st[N*20];

inline double get_k(point y,point x){

    return (y.y-x.y)/(y.x-x.x);

}

inline bool cmp(point a,point b){

    if(a.x!=b.x)return a.x<b.x;

    return a.y>b.y;

}

struct nd{int to,a,b;};

vector<nd>vec[N];

vector<point>pt,tp[2];

struct edge{

    int n,to;

    ll a,b;

}e[N<<1];

inline void add(int u,int v,int a,int b){

    e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].a=a;e[tot].b=b;

    e[++tot].n=head[v];e[tot].to=u;head[v]=tot;e[tot].a=a;e[tot].b=b;

}

inline void get_tb(int tag,int num){

  sort(cu[tag]+1,cu[tag]+num+1,cmp);

  tp[tag].clear();

  tp[tag].push_back(cu[tag][1]);

  int top=1;

  for(int i=2;i<=num;++i){

    if(cu[tag][i].x==tp[tag][top-1].x)continue;

    while(top>1&&get_k(cu[tag][i],tp[tag][top-2])>get_k(tp[tag][top-1],tp[tag][top-2]))tp[tag].pop_back(),top--;

    tp[tag].push_back(cu[tag][i]);top++;

  }

}

inline void merge(){

   point now=tp[0][0]+tp[1][0];

   pt.push_back(now);

   int sm=tp[0].size()+tp[1].size()-2,now1=0,now2=0;

   for(int i=1;i<=sm;++i){

    point xx,yy;

    if(now1+1<tp[0].size())xx=tp[0][now1+1]-tp[0][now1];

    if(now2+1<tp[1].size())yy=tp[1][now2+1]-tp[1][now2];

    if(now2+1>=tp[1].size()||((now1+1<tp[0].size())&&xx*yy<0))now=now+xx,now1++;

    else now=now+yy,now2++;

    pt.push_back(now);

   }

}

void dfs1(int u,int fa){

    int now=0;

    for(vector<nd>::iterator it=vec[u].begin();it!=vec[u].end();++it){

        int v=it->to,a=it->a,b=it->b;

        if(v==fa)continue;

        if(!now){add(u,v,a,b);now=u;}

        else{++num;add(now,num,0,0);add(num,v,a,b);now=num;}

        dfs1(v,u);

    }

}

void getroot(int u,int fa){

    size[u]=1;dp[u]=0;

    for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa&&!jin[i]){

        int v=e[i].to;

        getroot(v,u);

        size[u]+=size[v];

        if(max(size[v],sum-size[v])<rootval){

            root=i;

            rootval=max(size[v],sum-size[v]);

            _rootval=size[v];

        }

    }

}

void getdeep(int u,int fa,int tag,ll suma,ll sumb){

    bool tg=0;

    for(int i=head[u];i;i=e[i].n)if(e[i].to!=fa&&!jin[i]){

        int v=e[i].to;tg=1;

        getdeep(v,u,tag,suma+e[i].a,sumb+e[i].b);

    }

    if(!tg){

        cu[tag][++cuu[tag]]=point{suma,sumb};

    }

}

void solve(int rot,int S){

     int u=e[rot].to,v=e[rot^1].to;

     jin[rot]=jin[rot^1]=1;

     int sm1=_rootval,sm2=S-_rootval;

     cuu[0]=cuu[1]=0;

     getdeep(u,0,0,e[rot].a,e[rot].b);

     getdeep(v,0,1,0ll,0ll);

     get_tb(0,cuu[0]);

     get_tb(1,cuu[1]);

     merge();

     if(sm1!=1){

       sum=sm1;rootval=num;getroot(u,0);

       solve(root,sm1);

     }

     if(sm2!=1){

       sum=sm2;rootval=num;getroot(v,0);

       solve(root,sm2);

     }

}

int main(){

    n=rd();m=rd();

    if(n==1){

        for(int i=1;i<=m;++i)printf("0 ");

        return 0;

    }

    int x,y,a,b;

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

        x=rd();y=rd();a=rd();b=rd();

        vec[x].push_back(nd{y,a,b});

        vec[y].push_back(nd{x,a,b});

    }

    num=n;

    dfs1(1,0);

    root=0;sum=num;rootval=num;

    getroot(1,0);

    solve(root,num);

    sort(pt.begin(),pt.end(),cmp);

    for(vector<point>::iterator it=pt.begin();it!=pt.end();++it){

      point now=*it;

      if(!top){st[top=1]=now;continue;}

      if(now.x==st[top].x)continue;

      while(top>1&&get_k(now,st[top-1])>get_k(st[top],st[top-1]))top--;

      st[++top]=now;

    }

    for(int i=m-1;i>=0;--i){

      while(top>1&&get_k(st[top],st[top-1])<-i)top--;

      ans[i]=1ll*i*st[top].x+st[top].y;

    }

    for(int i=0;i<m;++i)printf("%I64d ",ans[i]);

    return 0;

}
巴特西

CF1019E Raining season

题解

代码

最新文章

热门文章
