首页 > 代码库 > bzoj 4449: [Neerc2015]Distance on Triangulation
bzoj 4449: [Neerc2015]Distance on Triangulation
Description
给定一个凸n边形，以及它的三角剖分。再给定q个询问，每个询问是一对凸多边行上的顶点(a,b)，问点a最少经过多少条边(可以是多边形上的边，也可以是剖分上的边)可以到达点b。
Input
第一行一个整数n（n <= 50000），代表有n个点。点1,2,3,…,n是凸多边形上是顺时针排布的。
接下来n-3行，每行两个整数(x,y)，代表(x,y)之间有一条剖分边。
接下来是一个整数q(q <= 100000)，代表有q组询问。
接下来q行是两个整数(a,b)。
Output
输出q行，每行一个整数代表最少边数。
类似边分治，每次选一条边将多边形分为两部分，处理经过边的端点的路线，递归分治
#include<bits/stdc++.h>char buf[70007],*ptr=buf+70000;int G(){ if(ptr-buf==70000)fread(ptr=buf,1,70000,stdin); return *ptr++;}int _(){ int x=0; if(ptr-buf<69900){ while(*ptr<48)++ptr; while(*ptr>47)x=x*10+*ptr++-48; }else{ int c=G(); while(c<48)c=G(); while(c>47)x=x*10+c-48,c=G(); } return x;}const int N=100007,inf=0x3f3f3f3f,P=293999;int n,qp,idp=0;int deg[N],q[N],ql=0,qr=0,as[N];std::vector<int>e0[N],ee[N];struct Q{int w,id;};std::vector<Q>qq[N];Q*qs[N][2];int sz[N],*lr[N][2],*et[N][2];int p3[N][3];void ae(int a,int b){ ++deg[b];++deg[a]; e0[a].push_back(b); e0[b].push_back(a);}struct hash_map{ int h[P][4]; int*operator()(int a,int b){ if(a>b)std::swap(a,b); int w=(a*1399+b*293)%P; while(h[w][0]){ if(h[w][0]==a&&h[w][1]==b)return h[w]+2; if((w+=1237)>=P)w-=P; } h[w][0]=a,h[w][1]=b; return h[w]+2; }}h1,h2;void chk(int a,int b){ if(a>b)std::swap(a,b); if(a==1&&b==n||a+1==b)return; int*w=h1(a,b); if(w[0]){ int x=idp,y=w[0]; ee[x].push_back(y); ee[y].push_back(x); int*c=h2(x,y); c[0]=a;c[1]=b; }else w[0]=idp;}int ss[N][2],sp,tk=1,ed[N],ed2[N];int ps[N],pp=0;void ins(int a){ for(int t=0;t<3;++t){ int w=p3[a][t]; if(ed2[w]!=tk)ed2[ps[pp++]=w]=tk; }}void f2(int w,int pa){ sz[w]=1; ed[w]=tk; ss[sp][0]=w,ss[sp++][1]=pa; for(int*l=lr[w][0],*r=lr[w][1];l!=r;++l){ int u=*l; if(u==pa)continue; f2(u,w); sz[w]+=sz[u]; }}void dele(int a,int b){ for(int*l=lr[a][0],*r=lr[a][1];l!=r;++l)if(*l==b){ *l=*--lr[a][1]; return; }}int min(int a,int b){return a<b?a:b;}void mins(int&a,int b){if(a>b)a=b;}int d1[N],d2[N],dd1[N],dd2[N],dk=1;bool qd[N];void bfs(int w,int*d,int*dd){ ql=qr=0; dd[q[++qr]=w]=dk,d[w]=0; while(ql!=qr){ w=q[++ql]; for(int*l=et[w][0],*r=et[w][1];l!=r;++l){ int u=*l; if(ed2[u]==tk&&dd[u]!=dk)dd[q[++qr]=u]=dk,d[u]=d[w]+1; } }}void f1(int w){ ++tk; pp=0; sp=0; f2(w,0); int SZ=sz[w]; if(SZ>1){ int mx=0,p1=w,p2=0; for(int i=0;i<sp;++i){ int u=ss[i][0],mv=min(sz[u],SZ-sz[u]); if(mv>mx)mx=mv,p1=u,p2=ss[i][1]; ins(u); } dele(p1,p2); dele(p2,p1); int*ns=h2(p1,p2); ++dk; bfs(ns[0],d1,dd1);bfs(ns[1],d2,dd2); for(int i=0;i<pp;++i){ int u=ps[i]; int d1u=d1[u]; int d2u=d2[u]; for(Q*l=qs[u][0],*r=qs[u][1];l!=r;++l){ int v=l->w; if(qd[v])*l--=*(qs[u][1]=--r); else if(ed2[v]==tk){ int d1v=d1[v]; int d2v=d2[v]; mins(as[l->id],min(min(d1u+d1v,d2u+d2v),min(d1u+d2v+1,d2u+d1v+1))); } } } qd[ns[0]]=qd[ns[1]]=1; for(int d=0;d<2;++d)qs[ns[d]][0]=qs[ns[d]][1]; f1(p1);f1(p2); }}int main(){ n=_(); for(int i=1,a,b;i<=n-3;++i){ a=_();b=_(); ae(a,b); } for(int i=1;i<=n;++i)ae(i,i==n?1:i+1); for(int i=1;i<=n;++i){ et[i][0]=e0[i].data(); et[i][1]=et[i][0]+e0[i].size(); } for(int i=1;i<=n;++i)if(deg[i]==2)q[++qr]=i; while(ql!=qr){ int w=q[++ql]; if(deg[w]!=2)break; deg[w]=0; int cs[3],cp=0; cs[cp++]=w; for(int*l=et[w][0],*r=et[w][1];l!=r;++l){ int u=*l; if(!deg[u])continue; cs[cp++]=u; if(2==--deg[u])q[++qr]=u; } ++idp; for(int i=0;i<3;++i){ for(int j=0;j<i;++j)chk(cs[i],cs[j]); p3[idp][i]=cs[i]; } } for(int i=1;i<=idp;++i){ lr[i][0]=ee[i].data(); lr[i][1]=lr[i][0]+ee[i].size(); } qp=_(); for(int i=0;i<qp;++i){ int x=_(),y=_(); if(x==y)continue; if(x>y)std::swap(x,y); if(x==1&&y==n||x+1==y||h1(x,y)[0]){ as[i]=1; continue; } as[i]=inf; qq[x].push_back((Q){y,i}); qq[y].push_back((Q){x,i}); } for(int i=1;i<=idp;++i){ qs[i][0]=qq[i].data(); qs[i][1]=qs[i][0]+qq[i].size(); } f1(1); for(int i=0;i<qp;++i)printf("%d\n",as[i]); return 0;}
bzoj 4449: [Neerc2015]Distance on Triangulation
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。