Complexity of your solution is O(N^2 * log N).

It is slow in this problem.

Refer to code snippet in editorial.

It contains simple O(N^2) solution without any data structures.

Firstly thanks for the reply,secondly could you please explain me how did you come up with that complexity…actually I thought that my complexity is O(N*log N)…considering the log N was the insertion time in the priority queue…Thanks in advance again…

At each step of algorithm (N-1 times) for each unvisited vertex you push pair (u, j) to the heap.

So total number of pushes is about N*N/2.

Also you should not take distance modulo MOD when create adjacency matrix.

Please read the editorial carefully (the bold sentence).

Thanks a lot…will keep in mind next time.

`k+=(a*a)`

should be `k += (long long)a * a`

`sum=(sum*k)%MOD`

should be `sum = k%MOD * sum % MOD`

But most likely after this it will get TLE.

thank you very very much for your help i made the changes and it worked…got ac after 10 wa

Congrats!

You were lucky to pass with O(N^2 * log N) solution which supposed to get TLE in this problem.

This is probably because of own-written heap class.

can you explain how the complexity comes out to be O(N^2 * log N) .as in the while loop i build the heap which is o(n)and this loop will occur n times so overall complexity should be O(n^2)

Your solution is quite unclear. But it seems to me that `maxheapify`

has complexity **O(log(n/i))** in the worst case. And `build`

call it for all i from 1 to n/2. So build has complexity O(n * log n).

Read editorial. Your mistakes are mentioned there.

When `maksi`

becomes zero you should break from the cycle.

Well of course Thanks Anton!

Thank you.

AC

I would really appreciate someone looking at the solution

When two towns have the same point, it’ll not connect those towns and give the initial answer which is 1.

I used kruskal and got ac in 3.91 sec…link to my solution

https://www.codechef.com/viewsolution/29236419

I have used Prim’s Algo with priority queue.Why is it giving TLE?

#include <bits/stdc++.h>

#include

#define lli long long int

#define mod 747474747

#define pb push_back

#define pp pop_back

#include

#include

#include <math.h>

#include <unordered_map>

using namespace std;

typedef pair<lli, lli> pi;

vector adj[7000];

vector dim[7000];

bool marked[7000];

lli prim(lli x)

{

priority_queue<pi, vector> Q;

lli maxCost = 1, cost = 0;

```
Q.push(make_pair(x, 1));
while(!Q.empty())
{
pi f = Q.top();
Q.pop();
lli y = f.second, x = f.first;
if(marked[x])
{
continue;
}
//maxCost = (maxCost*y)%mod;
//cost += y;
maxCost = (maxCost*y)%mod;
maxCost %= mod;
marked[x] = 1;
for(lli i = 0; i < adj[x].size(); i++)
{
y = adj[x][i].first;
if(marked[y] == false)
{
Q.push(adj[x][i]);
}
}
}
return maxCost%mod;
```

}

int main()

{

ios_base::sync_with_stdio(false);

cin.tie(NULL);

cout.tie(NULL);

```
lli t;
cin >> t;
while(t--){
//memset(marked, 0, sizeof(marked));
lli n, d, x;
cin >> n >> d;
for(lli i = 0; i < n; i++)
{
for(lli j = 0; j < d; j++)
{
cin >> x;
dim[i].pb(x);
}
}
lli dist = 0;
for(lli i = 0; i < n-1; i++)
{
for(lli j = i+1; j < n; j++)
{
for(lli k = 0; k < d; k++)
{
dist += pow((dim[i][k] - dim[j][k]), 2);
//dist += fmod((pow(fmod((fmod(dim[i][k] - dim[j][k]), mod) + mod), mod), 2), mod);
}
//dist = fmod(pow(dist, 1/2), mod);
adj[i].pb(make_pair(j, dist));
adj[j].pb(make_pair(i, dist));
dist = 0;
}
}
cout << prim(0) << endl;
}
return 0;
```

}