# HDELIVERY: Getting tle

Hi,

I am currently attempting the problem “Home delivery” from the March long contest. As soon as I saw it, I knew that all I needed was to use a Union-Find data structure. My code is very simple and straight forward, yet I am getting TLE. ( I have implemented both path-compression as well as union-by-rank in my union-find data structure )

I would be very grateful if anyone could suggest improvements to my code. Thank you

CODE :

``````import java.io.BufferedReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.StringTokenizer;

/*
Implements DisjointSet data structure using both Union by Rank as well
as Path Compression
*/

class DisjointSet
{
private int[] parent;
private int[] rank;
private int size;

public DisjointSet( int n )
{
size = n;
parent = new int[ n ];
Arrays.fill( parent, -1 );
rank = new int[ n ];
Arrays.fill( rank, -1 );
}

public void makeSet( int x )
{
parent[ x ] = x;
rank[ x ] = 0;
}

public int findRoot( int x )
{
if( parent[x] != x )
parent[ x ] = findRoot( parent[x]);

return parent[x];
}

public void Union( int x, int y )
{
int root1 = findRoot( x ) ;
int root2 = findRoot( y );

if( root1 != root2)
}

private void Link( int x, int y )
{
if( rank[ x ] < rank[ y ])  // Make y x's parent
{
parent[ x ] = y;
}

else if( rank[ x ] > rank[ y ])
{
parent[ y ] = x;
}

else
{
parent[ x ] = y;
rank[ y ]++;
}
}

}

public class Main
{
static int n, m;

public static void main( String[] args ) throws IOException
{

int T = Integer.parseInt( br.readLine() );
StringTokenizer tok;
String s;

while( T-- > 0 )
{
tok = new StringTokenizer( s );

n = Integer.parseInt( tok.nextToken() );
m = Integer.parseInt( tok.nextToken() );

DisjointSet d = new DisjointSet( n );
for( int i=0; i<n; i++ )
d.makeSet( i );

for( int i=0; i<m; i++ )
{
tok = new StringTokenizer( s );
int a = Integer.parseInt( tok.nextToken() );
int b = Integer.parseInt( tok.nextToken() );

if( a==b )
continue;

d.Union(a, b);
}

int q = Integer.parseInt( br.readLine() );

for( int i=0; i<q; i++ )
{
tok = new StringTokenizer( s );
int a = Integer.parseInt( tok.nextToken() );
int b = Integer.parseInt( tok.nextToken() );

if( d.findRoot(a) == d.findRoot(b))
System.out.println("YO");

else
System.out.println("NO");

}
}
}
}``````
1 Like

In this problem the queries are too large. Each time you are computing for the parent value thereby increasing the complexity. You could use pre-computation method to firstly generate all sorts of combination then answer the queries in O(1) time. I used Floyd-Warshall algorithm to get AC.

3 Likes

In your code does each query gets answered in O(1) time? To re-phrase does the running time of this line of code `d.findRoot(a) == d.findRoot(b)` depend on ‘n’ in the worst case or is it a constant always.

The easiest solution for me in this particular problem was to use BFS/DFS as described in the editorial.

I think you should have a look at my soution . I have solved it using Disjoint sets only and it was quite fast (0.81).

2 Likes

Thank you I went through your code, it’s more or less the same as mine I guess, but I will see if I can use tips from your code to optimize my own further

Thing is, I actually converted the entire solution to just doing a BFS once, and answering all the queries in constant time. I am still getting a TLE. Is it that StringTokenizer is making my code slow ? If so, could you please suggest some alternatives ?

Yes, I think you get TLE beacause taking input as a string and then parsing makes your code slow. I’ll recommend you to look at EgorK’s solution(http://www.codechef.com/viewsolution/873600). It will be good if you use c++ for online judges. I personally feel c++ has almost everything you will need during a contest. If you want to remain stuck to Java then atleast pick up those FastIO methods from EgorK’s code.

//