Religious poeple

#1

dont understand why this code is not working

#2

@sans_sehgal
Use long long int in your code and see if all the nodes that do not form an edge are being accounted for properly in your code as they wouldn’t be a part of your adjacency list and would require each a temple of its own.

#3

@tarunluthra i am sorry but you havent been very helpful. i have checked every test case that i can and for individual test cases the code has been working. howerver, when i submit the code it doesnt get submitted for some reason. it just comes back to the original screen. i tried doing this even with long long int but did not help. https://ide.codingblocks.com/s/166651

#4

@tarunluthra dont try debugging my code, it maybe too complicated. just tell me some test cases which aernt passing.

#5

@sans_sehgal
Try this testcase :
Input :
7
3 1 18 16
1 1
6 6 15 18
3 4
2 4
3 3
2 5
5 5
6 4
6 5 11 10
4 5
1 5
2 3
3 5
5 5
9 2 11 14
1 7
1 6
5 8 18 16
4 4
2 4
1 3
5 1
5 2
2 3
3 3
2 2
6 5 18 15
6 2
6 4
2 2
3 3
6 1
2 1 10 12
2 1

Expected Output :
54
90
62
99
82
99
20

#6

@tarunluthra hi, my code is still not passing all test cases please help https://ide.codingblocks.com/s/166651

#7

@sans_sehgal
Your code takes a very long time to run. While it is producing correct results , it is not at all optimised. You are calling the sameComponent function for each insertion. The called function does an entire BFS traversal of the graph and then decides whether to add the edge or not. There are ways to optimise this.
While your solution is correct , it is not at all optimised. I suggest you to think of some ways of solve this problem in lesser time.
I am sharing my approach to solve this problem so you can get an idea.

Count the number of disjoint components (subgraphs which are not connected to each other) and store them in a variable , say ‘components’
Each component must have a single Temple
So cost of temple in each component is a * components
Further there are (x-1) roads required in each component where x is no of vertices in that component
Sum of roads in all components = (n - components) , n is no of nodes in adjacency list
Multiply that with b , cost to repair each road
Cost so far , cost = a * component + b * (n-component)

But there are some vertices that do not form any edges
Some vertices which stand alone and each of these vertices must have a temple of its own
Since they do not form any edge , there count is not included in the adjacency list
No of such nodes is (V - n) …where V is total no of nodes and n is no of nodes that form an edge and are part of previously counted components
Since each of these nodes must have a temple
Total cost = a * component + b * (n-component) + a * (V-n)

Do not forget to consider the base case when a<=b

#8

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.