Dish Owner

I have used DSU to find the answer but it seems to repeatedly give WA .
Link : [https://www.codechef.com/viewsolution/26224386]
Where am I going wrong ?
Any help will be appreciated

Div 1 peeps asking to be spoonfed.
And I thought this was exclusive to greens and grays and sometimes blues.
Wow.

Your code for finding root(x) is not correct.
The bug is in the while loop of that function.
You are updating i = parent[i] but parent[i] is already updated in the line just above it.

I love the feigned outrage.
According to the dictionary , the definition of spoon-fed is

provide (someone) with so much help or information that they do not need to think for themselves.

I tried the problem multiple times with and without path compression , could not find any bug , checked the editorial ( it also used DSU ) , checked the previous discussions of the problem with a few five stars saying some issue was there and then took to discuss to ask my doubt .

I think it’s alright for anyone no matter how many “stars” they possess to look for help to get out of a block :slight_smile:

Maybe it’s a very small thing I overlooked , maybe I made a blunder , I will eventually figure out by myself anyway but I suggest politely that you refrain from passing comments like these :wink:

Any one irrespective of their stars when faced with a difficulty should be ready to ask questions . Isn’t that the point of a forum ? To grow , together ?

If you don’t agree , I respect your opinion . Ciao buddy :smile: Take care .

5 Likes

I tried all three ways before (including without path compression) and all give same result :frowning:

If you are still stuck…
There is an issue in your union method i guess
int a = root(x);
int b = root(y);
parent[a] = parent[b];

One thing more,
When you are checking for score, directly call union method to merge the dishes.
this should work fine.I faced the same problem while solving this.
Hope this helps.

He is just being salty, I am sure you are too humble to say that but you can say that ‘grapes are sour.’ :slight_smile: