author’s solution is giving TLE. i think path compression technique is not working. i also used that method and got tle.
pls check it.
no I think the problem was that: (this was your original code)
static int owner(int x)
{
if(p[x] == x)
return x;
else return p[x]=owner(p[x]);
}
here may be the problem was with assignment operator (i am not sure how it works but it works differently in java and C++).
System.out.println() is slow … use BufferedWriter or BufferedOutputStream for fast IO
see my code for reference :
http://www.codechef.com/viewsolution/4330077
i think you should use BufferdOutputStream instead of System.out.println
see my code for reference : CodeChef: Practical coding for everyone
1 Like
I think you should call your set union function with x and y…(not px and py)…and start your indices from 1(not 0) in array…look this solution CodeChef: Practical coding for everyone
i have posted it as an answer as the word limit on comments is too low
@shivam217 no,thats not the correct reason
Thanks a lot @shubham12 , I switched puts to cout and used the +1 trick and got AC 
Really, really thanks a lot 
And the seudo-code from editorial was also really well written Hope I can start doing this more often
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.
Authors’ solution for this problem is wrong. It gives TLE because it doesn’t use path compression.
2 Likes
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?
Hello,
Why i am getting nzec my code is in python and my logic is correct. can anyone please help me in this I am really frustuated.
here is my solution
here you go …CodeChef: Practical coding for everyone
The problem was running out of stack memory. This probably happened because of our approach to union-find(class and object) coz this was not happening in another solutions with same logic but array based approach.
Any how use sys.setrecursionlimit and it should give AC…read more into it
Consider Input as:
1
5
1 1 2 3 4
1
0 1 1
What should be the ouput of this? In short explain how to handle tie cases.
getting wrong answer, can someone share have any idea what went wrong or any test cases to test out CodeChef: Practical coding for everyone. thanks
anyone plz plz check why i am getting WA…
#include
#include
#include
#include
#include
#include
#include <math.h>
#include
#include
#include
#include
#include
#define f(i,n) for(int i=0;i<n;i++)
#define f1(i,a,b) for(int i=a;i<b;i++)
#define ld long double
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define mii map<int,int>
#define msi map<string,pair<int,int>>
#define pii pair<int,int>
#define F first
#define S second
#define PI 3.1415926535
typedef long long ll;
using namespace std;
int find1(int u,int *s)
{
int x=u;
while(s[x]>0)
{
x=s[x];
}
return x;
}
void union1(int x,int y,int arr[],int *s)
{
if(find1(x,s)!=find1(y,s))
{
if(arr[x]<arr[y])
{
s[find1(x,s)]=find1(y,s);
}
else if(arr[x]>arr[y])
{
s[find1(y,s)]=find1(x,s);
}
}
else
cout<<“Invalid query!”<<endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int arr[n+1];
for(int i=1;i<=n;i++)
{
cin>>arr[i];
}
int s[n+1];
for(int i=1;i<=n;i++)
{
s[i]=-i;
}
int q;
cin>>q;
while(q--)
{
int a;
cin>>a;
if(a==0)
{
int x,y;
cin>>x>>y;
// cout<<x<<" "<<y<<endl;
union1(x,y,arr,s);
}
else if(a==1)
{
int x;
cin>>x;
int r=find1(x,s);
cout<<r<<endl;
}
}
}
}