[BZOJ2791][Poi2012]Rendezvous

2791: [Poi2012]Rendezvous

Time Limit: 25 Sec  Memory Limit: 128 MB
Submit: 95  Solved: 71
[Submit][Status][Discuss]

Description

给定一个n个顶点的有向图,每个顶点有且仅有一条出边。
对于顶点i,记它的出边为(i, a[i])。
再给出q组询问,每组询问由两个顶点a、b组成,要求输出满足下面条件的x、y:
1. 从顶点a沿着出边走x步和从顶点b沿着出边走y步后到达的顶点相同。
2. 在满足条件1的情况下max(x,y)最小。
3. 在满足条件1和2的情况下min(x,y)最小。
4. 在满足条件1、2和3的情况下x>=y。
如果不存在满足条件1的x、y,输出-1 -1。

Input

第一行两个正整数n和q (n,q<=500,000)。
第二行n个正整数a[1],a[2],...,a[n] (a[i]<=n)。
下面q行,每行两个正整数a,b (a,b<=n),表示一组询问。

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

HINT

Source

鸣谢Oimaster

[Submit][Status][Discuss]

n个点,n条边且每个点都有出边,显然是环套树森林。

先dfs把环套树拆成一堆树,倍增LCA。

先将x,y两个点倍增到环上,然后判断即可。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define N 500050
 4 using namespace std;
 5 inline int read()
 6 {
 7     int x=0,f=1;char ch=getchar();
 8     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
 9     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
10     return x*f;
11 }
12 int n,fa[N][20],root,q,circle[N],deep[N];
13 int num[N],sum[N],tot,pos[N],vis[N];
14 void findcircle(int x)
15 {
16     int now=x;
17     for(;;x=fa[x][0])
18     {
19         if(vis[x]==now)break;
20         if(vis[x])return;
21         vis[x]=now;
22     }
23     tot++;
24     while(!circle[x])
25     {
26         circle[x]=x;
27         deep[x]=1;
28         num[x]=++sum[tot];
29         pos[x]=tot;
30         x=fa[x][0];
31     }
32 }
33 void dfs(int x)
34 {
35     if(deep[x])return;
36     dfs(fa[x][0]);
37     circle[x]=circle[fa[x][0]];
38     deep[x]=deep[fa[x][0]]+1;
39     for(int i=1;(1<<i)<deep[x];i++)
40     fa[x][i]=fa[fa[x][i-1]][i-1];
41 }
42 inline int lca(int x,int y)
43 {
44     if(deep[x]<deep[y])swap(x,y);
45     int t=deep[x]-deep[y];
46     for(int i=18;~i;i--)
47     if(t&(1<<i))x=fa[x][i];
48     if(x==y)return x;
49     for(int i=18;~i;i--)
50     if(fa[x][i]!=fa[y][i])
51     x=fa[x][i],y=fa[y][i];
52     return fa[x][0];
53 }
54 bool judge(int a,int b,int c,int d)
55 {
56     if(max(a,b)<max(c,d))return 1;
57     if(max(a,b)>max(c,d))return 0;
58     if(min(a,b)<min(c,d))return 1;
59     if(min(a,b)>min(c,d))return 0;
60     if(a>=b)return 1;
61     return 0;
62 }
63 int main()
64 {
65     n=read();q=read();
66     for(int i=1;i<=n;i++)
67     fa[i][0]=read();
68     for(int i=1;i<=n;i++)
69     findcircle(i);
70     for(int i=1;i<=n;i++)
71     if(!circle[i])dfs(i);
72     while(q--)
73     {
74         int x=read(),y=read();
75         if(pos[circle[x]]!=pos[circle[y]])
76         {
77             puts("-1 -1");
78             continue;
79         }
80         if(circle[x]==circle[y])
81         {
82             int t=lca(x,y);
83             printf("%d %d\n",deep[x]-deep[t],deep[y]-deep[t]);
84             continue;
85         }
86         int ans1=deep[x]-1,ans2=deep[y]-1,t=pos[circle[x]];
87         x=num[circle[x]];y=num[circle[y]];
88         int z1=(sum[t]+y-x)%sum[t],z2=sum[t]-z1;
89         if(judge(ans1+z1,ans2,ans1,ans2+z2))
90         printf("%d %d\n",ans1+z1,ans2);
91         else printf("%d %d\n",ans1,ans2+z2);
92     }
93 }

时间: 02-15

[BZOJ2791][Poi2012]Rendezvous的相关文章

BZOJ 2791 Poi2012 Rendezvous 倍增LCA

题目大意:给定一棵内向森林,多次给定两个点a和b,求点对(x,y)满足: 1.从a出发走x步和从b出发走y步会到达同一个点 2.在1的基础上如果有多解,那么要求max(x,y)最小 3.在1和2的基础上如果有多解,那么要求min(x,y)最小 4.如果在1.2.3的基础上仍有多解,那么要求x>=y 因此那个x>=y是用来省掉SPJ的,不是题目要求- - 容易发现: 如果a和b不在同一棵内向树上,显然无解,否则一定有解 定义根为从一个点出发能走到的第一个环上点,如果a和b的根相同,则到达LCA是

Bzoj 2789: [Poi2012]Letters 树状数组,逆序对

2789: [Poi2012]Letters Time Limit: 20 Sec  Memory Limit: 128 MBSubmit: 278  Solved: 185[Submit][Status][Discuss] Description 给出两个长度相同且由大写英文字母组成的字符串A.B,保证A和B中每种字母出现的次数相同. 现在每次可以交换A中相邻两个字符,求最少需要交换多少次可以使得A变成B. Input 第一行一个正整数n (2<=n<=1,000,000),表示字符串的长度

[BZOJ2797][Poi2012]Squarks

2797: [Poi2012]Squarks Time Limit: 10 Sec  Memory Limit: 64 MBSubmit: 211  Solved: 89[Submit][Status][Discuss] Description 设有n个互不相同的正整数{X1,X2,...Xn},任取两个Xi,Xj(i≠j),能算出Xi+Xj.现在所有取法共n*(n-1)/2个和,要你求出X1,X2,...Xn. Input 第一行一个正整数n (3<=n<=300).第二行n*(n-1)/2

POI2012 (持续更新中)

Distance Well Vouchers Cloakroom A Horrible Poem Rendezvous Fibonacci Representation Squarks

[BZOJ2793][Poi2012]Vouchers

2793: [Poi2012]Vouchers Time Limit: 20 Sec  Memory Limit: 64 MBSubmit: 316  Solved: 148[Submit][Status][Discuss] Description 考虑正整数集合,现在有n组人依次来取数,假设第i组来了x人,他们每个取的数一定是x的倍数,并且是还剩下的最小的x个.正整数中有m个数被标成了幸运数,问有哪些人取到了幸运数. Input 第一行一个正整数m (m<=1,000,000),下面m行每行一

[BZOJ2795][Poi2012]A Horrible Poem

2795: [Poi2012]A Horrible Poem Time Limit: 50 Sec  Memory Limit: 128 MBSubmit: 261  Solved: 150[Submit][Status][Discuss] Description 给出一个由小写英文字母组成的字符串S,再给出q个询问,要求回答S某个子串的最短循环节.如果字符串B是字符串A的循环节,那么A可以由B重复若干次得到. Input 第一行一个正整数n (n<=500,000),表示S的长度.第二行n个小

[BZOJ2792][Poi2012]Well

2792: [Poi2012]Well Time Limit: 40 Sec  Memory Limit: 64 MBSubmit: 137  Solved: 61[Submit][Status][Discuss] Description 给出n个正整数X1,X2,...Xn,可以进行不超过m次操作,每次操作选择一个非零的Xi,并将它减一. 最终要求存在某个k满足Xk=0,并且z=max{|Xi - Xi+1|}最小. 输出最小的z和此时最小的k. Input 第一行两个正整数n, m (1<=

TIBCO Rendezvous — 技术介绍

TIBCO Rendezvous — 技术介绍 1.1.1.      TIBCO Rendezvous — 技术介绍 TIBCO Rendezvous(或称为TIBCO RV)产品是一种中间件,它具有发布/订阅(Publish/Subscribe).基于主题寻址(Subject-Based Addressing) 和自定义数据信息(Self-Describing Data Messages)等专利技术功能,使不同应用平台上的信息在一个共享的虚拟总线Information Bus(TIB)上进行

[BZOJ2788][Poi2012]Festival

2788: [Poi2012]Festival Time Limit: 30 Sec  Memory Limit: 64 MBSubmit: 187  Solved: 91[Submit][Status][Discuss] Description 有n个正整数X1,X2,...,Xn,再给出m1+m2个限制条件,限制分为两类: 1. 给出a,b (1<=a,b<=n),要求满足Xa + 1 = Xb 2. 给出c,d (1<=c,d<=n),要求满足Xc <= Xd 在满足所