# TLE IN Gears

Can someone help me with the solution of gears? I used bfs and dfs in this question but got TLE. If this question use DSU then can you explain me how I can implement it

HERE is my c++ code ( its neat enough to understand)

#### You can refer DSU is you don’t know it from HERE

This tutorial is very good and easy to understand…

### You need to use DSU for checking if two elements are connected or not in O(log(n))

After that everything is just logic…
I can explain my full solution here but I think you try it once on your own and ping me back if still can’t get it…

Click to view

### How ? :-

Click to view

If you get a query having assigned same sign by you and the nodes are connected from some other path already (i.e. 0-0 or 1-1 ) then it blocks whole connected structure (make “bool isBlocked” of root of that structure TRUE

### How? :-

Click to view

In query three u can check direction of gear (+ or -) by checking if variable sign of both nodes are same or not

## MAIN ISSUE:-

#### query type 2 (connect them):

3-4
Now , here let’s assume u assigned “sign1” to 3 and “sign0” to 4
5-6
Here you assigned “sign1” to 5 and “sign0” to 6
3-5
and after that u get query 3-5 then you need to invert sign of all nodes in one of them to connect them properly (this prob is when u get same sign query for connecting two separate structures)

#### Hint for Soln of Main Issue O(logn):

Click to view

use “bool invert” of its root(before connecting) to invert a whole structure…

### PS: you need to do sign^=invert(root) for each root a node have… as a node can have log(n) roots at max( as discussed in DSU tutorial)… (we can modify find root function to check real sign)

#### Note :- My approach wont work with path compression ( why ? think yourself :D)

1 Like

I solved this question with and without path compression, but I didn’t see much difference in execution time.
Can anyone explain to me why?

1. With path compression: https://www.codechef.com/viewsolution/19401887

2. Without path compression: https://www.codechef.com/viewsolution/19401750

Refer to the link I gave under problem discussion thread for DSU. Use that.

sorry @vijju I again commented before seeing you answer… I was typing since a long time so…

Comment is a comment and ans is an answer xD. Gone are those days when one would be upset over such trivial things @l_returns

1 Like

#nested hide blocks for the first time xD

1 Like