We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Journey to the Moon
  5. Discussions

Journey to the Moon

Sort by

recency

|

514 Discussions

|

  • flashhammer
     + 0 comments

    You can always use a long long type in C++.

    #include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;


static inline int Count(const std::vector<int> &groups, int head)
    {
    return -groups[head];
    }

static int Find(std::vector<int> &groups, int node)
    {
    if (groups[node] < 0)
        return node;
    return (groups[node] = Find(groups, groups[node]));
    }

static void Union(std::vector<int> &groups, int a, int b)
    {
    int parentA = Find(groups, a);
    int parentB = Find(groups, b);

        if (parentA == parentB)
            return;

    int countA   = Count(groups, parentA);
    int countB   = Count(groups, parentB);
    int newCount = countA + countB;

        if (countA > countB) {
            groups[parentB] = parentA;
            groups[parentA] = -newCount;
        } else {
            groups[parentA] = parentB;
            groups[parentB] = -newCount;
        }
    }

int main(void)
    {
        int n, p;

        std::cin >> n >> p;
        std::vector<int> groups(n, -1);

        for (int i = 0; i < p; i++) {
            int a, b;
            std::cin >> a >> b;
            Union(groups, a, b);
        }

        long long total     = 0;
        long long prevCount = 0;
        for (int i = 0; i < n; i++) {
            if (Find(groups, i) == i) {
                int count = Count(groups, i);

                total     += count * prevCount;
                prevCount += count;
            }
        }

        std::cout << total << "\n";
    }

  • thakurtejveer1
     + 0 comments

    Has anyone successfully passed test case 11

    100000 2
    1 2
    3 4

    expected ans : 4999949998

    the expected output is 4,999,949,998, which exceeds the 32-bit integer limit (2,147,483,647). This seems to cause overflow in languages where int is 32-bit by default.

  • g_pit_kyle
     + 0 comments

    Test case 11 doesn't work with the function signature in rust. The answer is > i32::MAX.

  • fdaliran
     + 0 comments

    For python code, test case 11, if you use summation over and over for calculating the final results, you could use cummulative sum to avoid it. it will help you to speed up.

  • ayushjaiswal2021
     + 1 comment

    Runtime error on #11 testcase others are successfully executed

    int parent[100001]; int Size[100001];

    void make(int n){ for(int i=0;i

    int find(int vertex){ if(parent[vertex]==vertex)return vertex; return parent[vertex]=find(parent[vertex]); }

    void Union(int a,int b){ a=find(a); b=find(b); if(a==b)return ; if(Size[b]>Size[a])swap(a,b); parent[b]=a; Size[a]+=Size[b]; }

    int journeyToMoon(int n, vector> astronaut) { make(n);

    for(int i=0;i<astronaut.size();i++){
    if(find(astronaut[i][0])!=find(astronaut[i][1])){
        Union(astronaut[i][0],astronaut[i][1]);
    }
}
long long ans=0;
vector<int> a;
for(int i=0;i<n;i++){
    if(parent[i]==i){
        a.push_back(Size[i]);
    }
}
for(int i=0;i<a.size();i++){
    for(int j=i+1;j<a.size();j++)ans+=(a[i]*a[j]);
}
return ans;