bzoj 2167: 公交车站
发布时间:2020-12-14 03:21:11 所属栏目:大数据 来源:网络整理
导读:Description Z市交通不发达,所有公交路线覆盖的边竟然一个环也不包含,甚至该市的公交路线有可能会分为几个互不连通的块,这可真是不可思议。有一天,你突然听到一条消息,说你的M个同学被困在了Z市里,他们分别要从他们当前所在的点ai移动到他们想去的点bi
DescriptionZ市交通不发达,所有公交路线覆盖的边竟然一个环也不包含,甚至该市的公交路线有可能会分为几个互不连通的块,这可真是不可思议。有一天,你突然听到一条消息,说你的M个同学被困在了Z市里,他们分别要从他们当前所在的点ai移动到他们想去的点bi.于是你立刻调集资料,了解了Z市的形状和公交路线的分布,现在你要算出每个人到达目的地最少要换多少次车,或者告知那个人不能仅用公交车达到目的地。 Solution首先最优走法是经过 (lca) 的,那么刚开始肯定是尽量往上走 #include<bits/stdc++.h> using namespace std; template<class T>void gi(T &x){ int f;char c; for(f=1,c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1; for(x=0;c<='9'&&c>='0';c=getchar())x=x*10+(c&15);x*=f; } const int N=1e4+10; int n,m,Q,head[N],nxt[N*2],to[N*2],num=0,L[N],R[N],DFN=0,dep[N],fa[N][19]; int f[N][19],b[N],rt[N],tt=0;vector<int>S[N]; inline void link(int x,int y){nxt[++num]=head[x];to[num]=y;head[x]=num;} inline void dfs(int x){ b[L[x]=++DFN]=x; for(int j=1;j<=18;j++)fa[x][j]=fa[fa[x][j-1]][j-1]; for(int i=head[x],u;i;i=nxt[i]){ if(L[u=to[i]])continue; fa[u][0]=x;dep[u]=dep[x]+1;dfs(u); } R[x]=DFN; } inline int lca(int x,int y){ if(dep[x]<dep[y])swap(x,y); int deep=dep[x]-dep[y]; for(int i=18;i>=0;i--)if(deep>>i&1)x=fa[x][i]; if(x==y)return x; for(int i=18;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; return fa[x][0]; } struct data{int ls,rs,w;}tr[N*20]; inline void ins(int &x,int l,int r,int sa){ tr[++tt]=tr[x];x=tt;tr[x].w++; if(l==r)return ; int mid=(l+r)>>1; if(sa<=mid)ins(tr[x].ls,l,mid,sa); else ins(tr[x].rs,mid+1,r,sa); } inline int qry(int x,int sa,int se){ if(sa<=l && r<=se)return tr[x].w; int mid=(l+r)>>1; if(se<=mid)return qry(tr[x].ls,sa,se); if(sa>mid)return qry(tr[x].rs,se); return qry(tr[x].ls,mid)+qry(tr[x].rs,se); } int main(){ freopen("pp.in","r",stdin); freopen("pp.out","w",stdout); int x,y,z,ans=0; cin>>n>>m>>Q; for(int i=1;i<n;i++)gi(x),gi(y),link(x,y),link(y,x); dfs(1); for(int i=1;i<=n;i++)f[i][0]=i; for(int i=1;i<=m;i++){ gi(x);gi(y);z=lca(x,y); if(dep[z]<dep[f[x][0]])f[x][0]=z; if(dep[z]<dep[f[y][0]])f[y][0]=z; if(L[x]>L[y])swap(x,y); S[L[x]].push_back(L[y]); } for(int i=1;i<=n;i++){ rt[i]=rt[i-1]; for(int j=S[i].size()-1;j>=0;j--)ins(rt[i],1,n,S[i][j]); } for(int i=n;i>=1;i--){ x=b[i]; if(dep[f[x][0]]<dep[f[fa[x][0]][0]])f[fa[x][0]][0]=f[x][0]; } for(int j=1;j<=18;j++) for(int i=1;i<=n;i++)f[i][j]=f[f[i][j-1]][j-1]; while(Q--){ gi(x);gi(y);z=lca(x,y);ans=0; if(x==y){puts("0");continue;} for(int i=18;i>=0;i--){ if(dep[f[x][i]]>dep[z])x=f[x][i],ans+=1<<i; if(dep[f[y][i]]>dep[z])y=f[y][i],ans+=1<<i; } if((f[x][0]==x && x!=z)||(f[y][0]==y && y!=z)){puts("-1");continue;} if(x==z || y==z){printf("%dn",ans);continue;} if(L[x]>L[y])swap(x,y); printf("%dn",ans+1-(bool)(qry(rt[R[x]],L[y],R[y])-qry(rt[L[x]-1],R[y]))); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
相关内容
- Groovy探索之MOP 十三 Interceptor 三(1)
- Delphi 消除 Method 'Create' hides virtual meth
- 热血传奇Rungate源代码分析笔记。
- perl在linux下通过date获取当前时间
- 使用Delphi 6(C/C++ OK)创建视频文件(AVI等)的库或组件?
- golang.org/x/time/rate 使用说明
- perl – 什么是’sub bar {{_ _ [1] => $_ [2]}}`完全可以吗
- 2012 蓝桥杯【初赛试题】大数乘法
- perl socket传hash(use Storable)
- delphi服务程序(service)的调试方法