Оптимизация кода на C++ (C++11) на примере конкретной задачи

#include <iostream>
#include <vector>
#include <algorithm>

/*
 * Данная структура обусловлена форматом входных данных
 */
template <class T>
struct Triplet {
    T first;   // Город, в котором дорога начинается
    T second;  // Город, в котором дорога заканчивается
    T third;   // Цена строительства дороги
};

/*
 * Каждый элемент UnionFind это множество
 */
template <class T>
class UF_element {
public:
    T parent;   // представитель множества
    T size;     // размер множества

    UF_element() {}

    UF_element(T id)
            : size(1)
            , parent(id)
    {
    }
};

template <class T>
class UnionFind {
private:
    std::vector<UF_element<T>> Elements;
public:
/*
 * Сначала город состоит из микрорайонов, не соединенных дорогами
 */
    UnionFind(T n)
            : Elements(n + 1)
    {
        for (register T i = 1; i < n + 1; ++i) {
            Elements[i] = UF_element<T>(i);
        }
    }

/*
 * При первом вызове поиска родителя сокращаем путь до него. 
 *     первый поиск за О(log n),
 *     последующие вызовы за O(1)
 */
    T find(T id){
        UF_element<T>& current = Elements[id];

        while (current.parent != Elements[current.parent].parent){
            current.parent = Elements[current.parent].parent;
        }
        return current.parent;
    }

    void merge(T a, T b) {
        UF_element<T>& UF_elem_A = Elements[find(a)];
        UF_element<T>& UF_elem_B = Elements[find(b)];

        if(UF_elem_A.parent == UF_elem_B.parent)
            return;

        if(UF_elem_A.size < UF_elem_B.size) {
            UF_elem_A.parent = b;
            UF_elem_B.size += UF_elem_A.size;
        } else {
            UF_elem_B.parent = a;
            UF_elem_A.size += UF_elem_B.size;
        }
    }
};

template <typename T>
bool comp(const Triplet<T>& a, const Triplet<T>& b) {
    return (a.third < b.third);
}

template <typename T>
void kruskal(std::vector<Triplet<T>>& data, size_t& cost, size_t& count, const size_t& n) {
    UnionFind<T> N(n);

    for (size_t i = 0; i < data.size(); ++i) {
        if (N.find(data[i].first) != N.find(data[i].second)) {
            if (data[i].third) {         // если стоимость дороги не 0 (т.е дорога еще не построена)
                cost += data[i].third;   // увеличиваем стоимость постройки дорог
                ++count;                 // увеличиваем количество дорог, которые надо построить
            }

            N.merge(data[i].first, data[i].second);
        }
    }
}

/*
 * Парсер для любых неотрицательных целочисленных типов
 */
template <typename T>
void read_unlocked(T &out) {
    T c = getchar_unlocked();

    for (; '0' <= c && c <= '9' ; c = getchar_unlocked()) {
        if (c == ' ' || c == '\n')
            return;
        out = out * 10 + c - '0';
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);

    size_t count = 0, cost = 0;
    // Не забывайте обнулять переменные. Спасибо @ilammy
    unsigned int n = 0, m = 0;

    read_unlocked(n);
    read_unlocked(m);

    std::vector<Triplet<unsigned int>> input(m);

    for (size_t i = 0; i < m; ++i) {
        read_unlocked(input[i].first);
        read_unlocked(input[i].second);
        read_unlocked(input[i].third);
    }

    std::sort(input.begin(), input.end(), comp<unsigned int>);
    kruskal(input, cost, count, n);

    std::cout << cost << " " << count << '\n';
}

/*
 * Подходит для всех неотрицательных целочисленных типов:
 *     первый параметр - это число, которое необходимо вывести
 *     второй параметр - это символ, который надо добавить после числа
 */
template <typename T>
void write_unlocked(T inp, char last=' ') {
    if (!inp) {
        putchar_unlocked('0');
        putchar_unlocked(last);
        return;
    }

    T out = 0;
    unsigned char sz_inp = 0;
    // переворачиваем число
    for (; inp; inp /= 10, ++sz_inp) {
        out = (out << 3) + (out << 1) + inp % 10;
    }
    // печатаем число
    for (; out; out /= 10, --sz_inp) {
        putchar_unlocked(out % 10 + '0');
    }
    // выводим нули, если они были в числе
    for (;sz_inp; --sz_inp) {
        putchar_unlocked('0');
    }

    putchar_unlocked(last);
}