2 курс. Программирование на C++. Турнир 3, осень 2021

вход курсы / турниры задачи участники консоль модули компиляторы ключевые слова результаты

ru en cn

5945032

Пользователь

Скопин Семён Андреевич

Время

31.12.2021 14:53 (27 д. 14:53)

Обработка

14:53 ... 14:53 (4,32 сек.)

Файл

5945032.cpp (CLang++ 5.0.0 + Address Sanitizer)

Турнир

2 курс. Программирование на C++. Турнир 3, осень 2021

Задача

D: Graph visitor

Набор тестов

Ограничения

Время: 1с Память: 4000Мб

Состояние [?]

Принято

код | результаты

[печатать | | ]

≡

#pragma once
#include <memory>
#include <unordered_map>

template<class Vertex>
class BfsVisitor {
 public:
    BfsVisitor() {
        data = std::make_shared<VisitorData>();
        data->start_v = 999;
    }
    void ExamineVertex(const Vertex& vertex) {
        if (data->start_v == 999) {
            data->start_v = Vertex(vertex);
        } else {
            data->start_v = vertex;
        }
    }

void DiscoverVertex(const Vertex& vertex) {
        if (data->start_v == 999) {
            data->tree.insert({vertex, vertex});
        } else {
            data->tree.insert({vertex, data->start_v});
        }
    }

size_t DistanceTo(const Vertex& target) const {
        size_t distance = 0;
        for (Vertex v = target; v != data->tree.at(v); v = data->tree.at(v)) {
            distance++;
        }
        return distance;
    }

Vertex Parent(const Vertex& vertex) const {
        return data->tree.at(vertex);
    }

private:
    struct VisitorData {
        Vertex start_v;
        std::unordered_map<Vertex, Vertex> tree;
    };

std::shared_ptr<VisitorData> data;
};

(1 107 b)

0.052s 0.014s 9