question:https://www.codechef.com/problems/ICPC16B

solution:

https://www.codechef.com/viewsolution/25034777

I requested you in this post to provide a submission link.

Also explain your solution briefly if you really want any sort of help from the community.

Finally, your code looks to be O(n^3) per test case. Think of a different solution or if youâ€™re really stuck look at the editorial.

Edit:

Hint: If a and b are in the array then a*b is also in the array. If a and a*b are present in the array, a*a*b is also in the array.

for:

1

2 3 4 5

your code gives : No

for:

1

5 2 3 4

your code gives: Yes.

See, why that is and debug your code.

Hi @psaini72 @sikh_coder

please can you guys help me to find the reason for wrong answer

problem link

my approach is to use co-ordinate compression and dsu.

my solution

## Solution

```
#include <bits/stdc++.h>
using namespace std;
int q;
int sz[1000100];
int rt[1000010];
void init(int n){
for(int i=0;i<=n;i++){
sz[i] = 1;
rt[i] = i;
}
}
int find(int x){
while(x!=rt[x])x=rt[x];
return rt[x];
}
void merge(int p,int q){
int x = rt[p];
int y = rt[q];
if(x == y)return;
if(sz[x] > sz[y])swap(x,y);
sz[y]+=sz[x];
sz[x] = 0;
rt[x] = rt[y];
}
int main()
{
cin >> q;
vector<pair<int,int>>v(q);
vector<int>aux;
for(int i=0;i<q;i++)
{
int p,q;
cin >> p >> q;
aux.push_back(p);
aux.push_back(q);
v[i].first = p;
v[i].second = q;
}
sort(aux.begin(),aux.end());
map<int,int>mp;
int cnt=1;
for(int i=0;i<aux.size();i++){
if(i==0 || aux[i]!=aux[i-1]){
mp[aux[i]] = cnt++;
}
}
for(int i=0;i<q;i++){
v[i].first = mp[v[i].first];
v[i].second = mp[v[i].second];
}
init(cnt);
for(int i=0;i<q;i++){
merge(v[i].first, v[i].second);
cout<<sz[find(v[i].first)]<<"\n";
}
}
```

Donâ€™t really understood your code:

hereâ€™s how I did it using weighted union and path compression:

I donâ€™t think this a fancy problem or such.Itâ€™s fairly straightforward. The only thing is that here size is till 10^9. So, what does that tell you? donâ€™t make an array. use a map. and thatâ€™s what I did.

https://www.hackerrank.com/challenges/friend-circle-queries/submissions/code/112958721

You are trolling arenâ€™t you?

Open a separate topic. Donâ€™t use this one. Provide a submission link (details tag is fine but I would still prefer a submission link). If you have already opened a topic and no one replied, just reply to it once again with something like â€śbumpâ€ť so that is shows up on the home page and more people will look at it.

Edit: In your merge function, it should be `int x = find(p)`

becuase after merging, you only update the roots of the roots. Not the whole tree. Could be that this is not the only error.

Yes,that is why I used coordinate compression.

I was reading this post and it was on open tab and I asked ,I thought itâ€™s fine to ask anywhere . But will do next time â€¦

Edit: thanks got it

I donâ€™t think you need to do that here:

## My Solution

```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fastio std::ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test int t;cin>>t;while(t--)
map<ll,ll> dsu;
ll max_len=INT_MIN;
map<ll,ll> size_ofSet;
int root(ll x) //path-compressed
{
while(dsu.find(x)!=dsu.end() && dsu[x]!=x)
{
dsu[x]=dsu[dsu[x]];
x=dsu[x];
}
return x;
}
void weighted_union(ll a,ll b) //weighted
{
ll root_A=root(a);
ll root_B=root(b);
if(root_A==root_B) return;
if(dsu[root_A]==0) dsu[root_A]=root_A;
if(dsu[root_B]==0) dsu[root_B]=root_B;
//cout<<root_A<<" "<<root_B<<"\n";
if(size_ofSet[root_A]==0) size_ofSet[root_A]=1;
if(size_ofSet[root_B]==0) size_ofSet[root_B]=1;
if(size_ofSet[root_A]>size_ofSet[root_B])
{
dsu[root_B]=dsu[root_A];
size_ofSet[root_A]+=size_ofSet[root_B];
max_len=max(max_len,size_ofSet[root_A]);
}
else
{
dsu[root_A]=dsu[root_B];
size_ofSet[root_B]+=size_ofSet[root_A];
max_len=max(max_len,size_ofSet[root_B]);
}
}
int main() {
fastio;
test{
ll a,b;cin>>a>>b;
weighted_union(a,b);
cout<<max_len<<"\n";
}
return 0;
}
```

thanks so if i write k=l+1 instead of k=1 than the output for the inputs you give will be correct but still it is showing wrong answer when i submit it so can you please tell me where i get it wrong