[ccJULY14] Chef and Frogs

描述 Description

Nobody knows, but N frogs live in Chef’s garden.

Now they are siting on the X-axis and want to speak to each other. One frog can send a message to another one if the distance between them is less or equal to K.

Chef knows all P pairs of frogs, which want to send messages. Help him to define can they or not!

Note : More than 1 frog can be on the same point on the X-axis.

输入格式 InputFormat

The first line contains three integers N, K and P.

The second line contains N space-separated integers A1, A2, …, AN denoting the x-coordinates of frogs“.

Each of the next P lines contains two integers A and B denoting the numbers of frogs according to the input.

输出格式 OutputFormat

For each pair print “Yes” without a brackets if frogs can speak and “No” if they cannot.

样例输入 SampleInput

5 3 3
0 3 8 5 12
1 2
1 3
2 5

样例输出 SampleOutput

Yes
Yes
No

CodeChef FROGV

用并查集判断。

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int i,j,t,n,m,l,r,k,z,y,x;
pair <int,int> a[100005];
int fa[100005];
int p;
int getfa(int s)
{
    if (fa[s]==s) return s;
    else fa[s]=getfa(fa[s]);
    return fa[s];
}
int main()
{
    scanf("%d%d%d",&n,&k,&p);
    for (i=1;i<=n;i++) scanf("%d",&a[i].first),a[i].second=i,fa[i]=i;
    sort(a+1,a+n+1);
    for (i=2;i<=n;i++) if (a[i].first-a[i-1].first<=k)
    {
        fa[a[i].second]=a[i-1].second;
    }
    for (i=1;i<=p;i++)
    {
        scanf("%d%d",&x,&y);
        if (getfa(x)==getfa(y)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}