CHEFGAME - Editorial

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…:slight_smile:

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).

1 Like

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

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.

1 Like

When maksi becomes zero you should break from the cycle.

1 Like

Well of course :smiley: Thanks Anton!

Thank you.
AC :slight_smile:

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 got AC using Kruskal.
Here’s my code link:

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

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

#include <bits/stdc++.h>
#define lli long long int
#define mod 747474747
#define pb push_back
#define pp pop_back
#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));

    pi f =;
    lli y = f.second, x = f.first;
    //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)
return maxCost%mod;


int main()

lli t;
cin >> 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;
    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;