I tried to follow the pseudo-code given above and implement the code for UF… But I’m getting WA… Can anyone tell me if something is very, very wrong here?
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
vector<int> parent(MAXN);
vector<int> S(MAXN);
int query,x,y,N,Q,px,py;
int find(int i)
{
int j;
if(parent[i]==i)
return i;
else
{
j=find(parent[i]);
parent[i]=j;
return j;
}
}
void set_union(int i, int j)
{
int x1,y1;
x1 = find(i);
y1 = find(j);
//parent of both of them will be the one with the highest score
if(S[x1]>S[y1])
parent[y1]=x1;
else if(S[x1] < S[y1])
parent[x1]=y1;
}
void init(int N)
{
S.resize(N);
parent.resize(N);
for(int i = 0; i < N;i++)
parent[i]=i;
}
void solve(int query)
{
if(query == 0)
{
cin >> x >> y;
x--; y--;
px = find(x);
py = find(y);
if(px == py)
puts("Invalid query!");
else
set_union(px,py);
}
else
{
cin >> x;
x--;
cout << find(x) << endl;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while(t--)
{
cin >> N;
init(N);
for(int i = 0; i < N; i++)
{
cin >> S[i];
}
cin >> Q;
while(Q--)
{
cin >> query;
solve(query);
}
}
return 0;
}
@kuruma thanks for this question i learnt something new.
first tiny mistake is the output of second query type you should print find(x)+1 as your numbers are 0-based .
secondly you have used “ios_base::sync_with_stdio(false)” that seems to cause your output to be buffered and is printed together only when the program terminates.
this would have been correct had you used puts/printf in output of 2nd query as well. since you used cout that output is not buffered and printed instantly while the output of all first queries is printed in the end.
So what you can do:
1.use fflush(stdout) after puts statement
2.use cout
3.NOT use ios_base::sync_with_stdio(false);
4.use puts/printf in the output of 2nd query as well
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
I have solved with the same approach but was getting TLE as i was using Console.WriteLine to print all the output in C# . When i used the StringBuilder to store the messages and output in the last it passed the test cases. I am not sure if we have to consider this small optimization also
@dev8546: Thanks for your comment. Now I understand the reason that I never got it AC. I couldn’t think that Console.WriteLine() might be causing the problem. I kept on hitting my head thinking there might be a better optimized way to solve the problem and finally gave up on it after trying some micro optimizations
Did the same in Java as dev8546 described. By printing System.out.println() it gets TLE. If i use a stringbuilder and output it at the end it passes. (I used both path compression and union by rank).
don’t use System.out.println(), instead use StringBuilder to store answers and then in the end use System.out.println() to print StringBuilder object. I have modified your code it has got accepted.
Link to ur code: CodeChef: Practical coding for everyone
(see the accepted solution).