网站开发项目经验描述,站长工具百科,wordpress 换语言包,免费高清logo在线观看【BZOJ2791】[Poi2012]Rendezvous Description 给定一个n个顶点的有向图#xff0c;每个顶点有且仅有一条出边。对于顶点i#xff0c;记它的出边为(i, a[i])。再给出q组询问#xff0c;每组询问由两个顶点a、b组成#xff0c;要求输出满足下面条件的x、y#xff1a;1. 从顶…【BZOJ2791】[Poi2012]Rendezvous Description 给定一个n个顶点的有向图每个顶点有且仅有一条出边。对于顶点i记它的出边为(i, a[i])。再给出q组询问每组询问由两个顶点a、b组成要求输出满足下面条件的x、y1. 从顶点a沿着出边走x步和从顶点b沿着出边走y步后到达的顶点相同。2. 在满足条件1的情况下max(x,y)最小。3. 在满足条件1和2的情况下min(x,y)最小。4. 在满足条件1、2和3的情况下xy。如果不存在满足条件1的x、y输出-1 -1。 Input 第一行两个正整数n和q (n,q500,000)。第二行n个正整数a[1],a[2],...,a[n] (a[i]n)。下面q行每行两个正整数a,b (a,bn)表示一组询问。 Output 输出q行每行两个整数。 Sample Input 12 5 4 3 5 5 1 1 12 12 9 9 7 1 7 2 8 11 1 2 9 10 10 5 Sample Output 2 3 1 2 2 2 0 1 -1 -1 题解由于给出的是个基环树森林所以我们考虑如下几种情况。 1.最终不会走到一个环上-1。2.还没走到环上就相遇那么我们用倍增当成树上LCA来处理即可。3.走到环上才相遇那么相遇点一定是两人刚走到环上时的两个点中的一个判一下即可。 #include cstdio
#include cstring
#include iostream
#include queue
#include vector
using namespace std;
const int maxn500010;
int n,m,sum,cnt;
int r[20][maxn],to[maxn],next[maxn],head[maxn],Log[maxn],bel[maxn],pos[maxn],len[maxn],toc[maxn],d[maxn];
queueint q;
vectorint v[maxn];
inline void add(int a,int b)
{to[cnt]b,next[cnt]head[a],head[a]cnt;
}
inline int lca(int a,int b)
{if(d[a]d[b]) swap(a,b);for(int iLog[d[a]-d[b]];i0;i--) if(d[r[i][a]]d[b]) ar[i][a];if(ab) return a;for(int iLog[d[a]];i0;i--) if(r[i][a]!r[i][b]) ar[i][a],br[i][b];return r[0][a];
}
inline bool cmp(int x1,int y1,int x2,int y2)
{if(max(x1,y1)!max(x2,y2)) return max(x1,y1)max(x2,y2);if(min(x1,y1)!min(x2,y2)) return min(x1,y1)min(x2,y2);return x1y1;
}
inline int rd()
{int ret0,f1; char gcgetchar();while(gc0||gc9) {if(gc-) f-f; gcgetchar();}while(gc0gc9) retret*10(gc^0),gcgetchar();return ret*f;
}
int main()
{nrd(),mrd();memset(head,-1,sizeof(head));int i,j,u,a,b,x,y,x1,y1,x2,y2;for(i1;in;i) r[0][i]rd(),d[r[0][i]];for(i2;in;i) Log[i]Log[i1]1;for(j1;(1j)n;j) for(i1;in;i) r[j][i]r[j-1][r[j-1][i]];for(i1;in;i) if(!d[i]) q.push(i);while(!q.empty()){uq.front(),q.pop();d[r[0][u]]--;if(!d[r[0][u]]) q.push(r[0][u]);}for(i1;in;i) if(d[i]!bel[i])for(sum,ji;!bel[j];jr[0][j]) pos[j]len[sum],bel[j]sum;for(i1;in;i){if(bel[i]) d[i]0,toc[i]i,q.push(i);else add(r[0][i],i);}while(!q.empty()){uq.front(),q.pop();for(ihead[u];i!-1;inext[i]) d[to[i]]d[u]1,toc[to[i]]toc[u],q.push(to[i]);}for(i1;im;i){ard(),brd();if(bel[toc[a]]!bel[toc[b]]) printf(-1 -1\n);else if(toc[a]toc[b]){xlca(a,b);printf(%d %d\n,d[a]-d[x],d[b]-d[x]);}else{xd[a],atoc[a],yd[b],btoc[b];x1x(pos[b]-pos[a]len[bel[a]])%len[bel[a]],y1y;x2x,y2y(pos[a]-pos[b]len[bel[b]])%len[bel[b]];if(cmp(x1,y1,x2,y2)) printf(%d %d\n,x1,y1);else printf(%d %d\n,x2,y2);}}return 0;
}//12 5 4 3 5 5 1 1 12 12 9 9 7 1 7 2 8 11 1 2 9 10 10 5 转载于:https://www.cnblogs.com/CQzhangyu/p/7814389.html
