6 test case failed

#1

I have implemented this using disjoint set. I united all x and y as given in question. Then for each city I called its superparent and found what is the size of that component.

AS many cities may have same super parent so I used set. If a compnent has 4 cities then
for i=1 to 4
{cost=min(cost,(Ai +B(n-i)));}
total ans+=cost.
I need to minimize my cost function which is either build road or temple. If a tample is build I can reduce on e road or vice versa.
sample cases passed and 1 final test case also.

#2

there is some problem with cost variable initialization, it wont work for int max certainly, but it is not working for inf as well. so I figured out some other way. check it.
int cost , res = 0;
while (!s.empty()) {
int spx = s.begin();
int n = d.sz[spx];
cost = an;
for (int i = 1; i < n; i++) {
cost = min(cost, (a * i) + b * (n - i));
}
res += cost;
s.erase(s.begin());
}

Moreover
you can optimize this code a bit more. as you can observe , to get the min cost , you dont need to run a loop from 1 to n. it can be done in o(1) time.
see, if A>B, then the min cost will be A+(n-1)B, else min cost will be nA.
so simply cost = min(A+(n-1)B, nA);

comment for loop and write
res += min(a + b * (n - 1), n*a);

thanks

#3

Well I tried this approach previously also and then it not worked. Today it worked and submitted everywhere sucessfully. Thanks a lot.

#4

please resolve and rate it if satisfied. thanks