DISHOWN - Editorial

Hello,

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;
}

Thanks in advance,

Bruno

@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

1 Like

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.

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

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.

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;
}
}
}
}

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

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

LEARN PATH_COMPRESSION from Topcoder

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

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

2 Likes

I have used same approach but I am getting TLE CodeChef: Practical coding for everyone please help me!

@mtbar131 : You didnt use path compression. That’s what I could notice.

@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 :frowning:

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).

2 Likes

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

1 Like

Just a quick check - Is this true with all languages or just the managed ones like C#/JAVA?

yeah …the path compression heuristics…really had an opportunity to learn… btw real thanx. :slight_smile:

1 Like

@sousnake: thanks :slight_smile: bad that i missed this because of System.out.println() :frowning: