it can be solved with union-find method too and it’s implementation is very easy…
#include<stdio.h>
void sort(int b[], int n)
{
int i,j;
int temp;
for(i=1;i<=n-1;i++)
{
for(j=1;j<=n-i-1;j++)
{
if(b[j]>b[j+1])
{
temp = b[j];
b[j] = b[j+1];
b[j+1] = temp;
}
}
}}
int main()
{
int n,k,p,a[100005],i,frog[2],c1=0,c2=0;
int n1,n2,b[100005],diff1=0,diff2=0;
scanf("%d%d%d",&n,&k,&p);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(i=1;i<=n;i++)
{
b[i] = a[i];
}
sort(b,n+1);
while(p--)
{
scanf("%d%d",&n1,&n2);
if(1<=n1<=n && 1<=n2<=n)
{
frog[0] = a[n1];
frog[1] = a[n2];
c1 = 1;
for(i=1;i<=n;i++)
{
if(b[i]!=frog[0])
c1++;
else break;
}
c1 =c1;
c2 = 1;
for(i=1;i<=n;i++)
{
if(b[i]!=frog[1])
c2++;
else break;
}
c2 = c2;
diff1 = c2 - c1;
diff2 = 0;
for(i=c1;i<c2;i++)
{
if(b[i+1]-b[i]<=k)
diff2++;
else break;
}
if(diff1==diff2)
printf("Yes\n");
else
printf("No\n");
}
}
}
what is wrong in this code
`` codeblocks giving right answer
every test case is satisfied
It’s simple just calculate the distance between every from…and if it is more than the value of k than the message can not be transferred
It can also be done with the help of DSU data structure.
Hello People,
I have tried this problem almost 3 times with the logic give by @brobear1995 still get WA. Please help me out. Link to the solution.
Can anyone tell me why the algorithm given below gives TLE…?
let all a[i] form the nodes of an undirected graph.
create a c++ set for all unvisited nodes.(initially containing all a[i])
initialize vis[] by all -1
now, call dfs for all nodes having vis[node]==-1
& set vis[node]=caller function to ensure that vis[node] will have same value for all nodes forming a connected component.
In dfs, recur for all nodes currently in unvisited(set) which have abs(a[i]-node)<=k.
Finally, for each query x and y:
if(vis[x]==vis[y])–>yes
else–>no
Can someone help me with this code?
I tried many cases myself and I am getting the desired answer.
But on submission it is showing WA.
Please help.