# 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