DISHOWN - Editorial

editorial
, , , , ,
41

Thanks a lot @shubham12 , I switched puts to cout and used the +1 trick and got AC :smiley:

Really, really thanks a lot :slight_smile: And the seudo-code from editorial was also really well written :smiley: Hope I can start doing this more often

42

glad i could help :). though i had some incorrect understanding of the
effect of “ios_base::sync_with_stdio(false)”.
i have to read it up.

43

@shubham12 thanks for pointing out the mistake…

44

Authors’ solution for this problem is wrong. It gives TLE because it doesn’t use path compression.

1 Like
45

What is the need of using find() function again in set_union() when we are already passing set_union() the parents of the 2 dishes?

46

http://www.codechef.com/viewsolution/7146440

I am getting runtime error.

can any check my code, i don’t know in what test case i am getting this error.

47

https://www.codechef.com/viewsolution/9892837
i’m getting tle i used same logic of editorial.Please help me
Thanks in advance.

48

I don’t know while my code is getting TLE.

Can anyone please help? Here is my link of code:

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

Thanks.

49

can anyone tell me whats wrong in solution :
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define FOR(a,b) for(i=a;i<b;i++)
#define RFOR(a,b) for(i=a;i>=b;i–)
#define MOD 1000000007
using namespace std;
typedef vector V;
typedef long long i64;
const long long LINF = (long long)1e16 + 5;
const int maxn=1e5+1;
int arr[1000000],score[1000000],n;
void initialize()
{
for(int i=0;i<n;i++)
{
arr[i]=i;
}
}
int root(int x)
{
int y = x;
while (x != arr[x]) {
x = arr[x];
}
for (;y != x;) {
int t = arr[y];
arr[y] = x;
y = t;
}
return x;
}

int main()
{
int t;
cin>>t;
while(t–)
{
int i,q,root_l,root_r;
cin>>n;
for(i=0;i<n;i++)
{
cin>>score[i];
}
initialize();
cin>>q;
while(q–)
{
int x,l,r;
cin>>x;
if(x==0)
{
cin>>l>>r;
–l,–r;
root_l=root(l);
root_r=root®;
if(root_l==root_r)
cout<<“Invalid query!\n”;
else
{
if(score[root_l]>score[root_r])
{
arr[root_r]=root_l;
}
else if(score[root_l]<score[root_r])
{
arr[root_l]=root_r;
}
}
}
else
{
cin>>l;
root_l=root(l);
cout<<root_l+1<<endl;
}
}
}
}

50

Can Someone point out the mistake in my code?plz
https://www.codechef.com/viewsolution/14346397

51

Can anyone explain me the meaning of this statement?
. Each of the chefs can then choose any one dish to battle against the other chef and the one having the dish with the higher score will win this round

52

LEARN PATH_COMPRESSION from https://www.topcoder.com/community/data-science/data-science-tutorials/disjoint-set-data-structures/

53

Hey I’m getting WA for the following


[1]. What could be the problem? 
I'm using path compression in root function.


  [1]: https://www.codechef.com/viewsolution/23624285