Почему я получаю ошибку времени выполнения на школьном сервере, а не на больших серверах, таких как HackerEarth или HackerRank, для этого минимального кода связующего дерева? - PullRequest
Новая
       40

Почему я получаю ошибку времени выполнения на школьном сервере, а не на больших серверах, таких как HackerEarth или HackerRank, для этого минимального кода связующего дерева?

0 голосов
/ 04 февраля 2019

Я получил домашнее задание, где мне нужно было написать программу, чтобы найти MST графика.Я попытался запустить его на школьном сервере, но я получил ошибку во время выполнения.Однако на больших серверах, таких как HackerEarth или HackerRank, я получил правильные ответы на все тестовые случаи.Граница для числа ребер и вершин равна 100000, а для веса ребра 10000. Вершины помечены от 0 до n.

Вот мой код: 

#include <stdio.h>
#include <algorithm>

using namespace std;

class Edge
{
    public:
        int x, y;
        long long w;
        bool operator<(const Edge& next) const;
};

bool Edge::operator<(const Edge& next) const
{
    return this->w < next.w;
}

class DisjointSet
{
    public:
        int parent, rank;
};

DisjointSet set[100100];
Edge edges[100100];

int findWithPathCompression(int x)
{
    if(set[x].parent != x)
        set[x].parent = findWithPathCompression(set[x].parent);

    return set[x].parent;
}

bool unionByRank(int x1, int y1)
{
    int x = findWithPathCompression(x1);
    int y = findWithPathCompression(y1);

    if(x == y)
        return false;

    if(set[x].rank > set[y].rank)
        set[y].parent = x;
    else if(set[y].rank > set[x].rank)
        set[x].parent = y;
    else
    {
        set[y].parent = x;
        set[x].rank++;
    }   

    return true;
}

int main()
{
    int n, m, e = 0, c = 0;
    long long r = 0;
    scanf("%d %d",&n,&m);

    for(int i = 0; i <= n; i++)
    {
        set[i].parent = i;
        set[i].rank = 1;
    }   

    for(int i = 0; i < m; i++)
    {
        scanf("%d %d %lld",&edges[i].x,&edges[i].y,&edges[i].w);
        edges[i].x;
        edges[i].y;
    }   

    sort(edges,edges + m);

    while(e != n - 1)
    {
        if(unionByRank(edges[c].x,edges[c].y))
        {
            r += edges[c].w;
            e++;
        }

        c++;
    }

    printf("%lld\n",r);
}
...