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

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

ru en cn

5945491

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

Thanks to the CWC partners from the GreenTeaNeko

Время

14:24<< 31.12.2021 19:21 (27 д. 19:22)

Обработка

19:21 ... 19:21 (3,24 сек.)

Файл

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

Турнир

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

Задача

D: Graph visitor

Набор тестов

Ограничения

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

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

Принято

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

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

≡

#include <unordered_map>
#include <iostream>
#include <unordered_set>
#include <vector>
#include <queue>
#include <exception>
#include <map>
#include <memory>
#include <utility>

template <class Vertex>
class BfsVisitor {
 private:
  class Vert {
   public:
    std::map < int, std::pair < int, int >> vertex;
    int a;
    int b = 0;
  };
  std::shared_ptr<Vert> vrt;

public:
  BfsVisitor() {
  vrt = std::make_shared<Vert>();
  vrt->a = 0;
  vrt->b = 0;
  }

void ExamineVertex(const Vertex &vr) {
    vrt->a = vr;
    vrt->b = vrt->vertex[vr].second + 1;
  }

void DiscoverVertex(const Vertex &vr) {
    if (vr == 0) {
      vrt->vertex.insert(std::make_pair(0,
      std::make_pair(0, 0)));
    } else if (vrt->vertex.find(vr) != vrt->vertex.end()) {
        if (vrt->b < vrt->vertex[vr].second) {
        vrt->vertex[vr].first = vrt->a;
        vrt->vertex[vr].second = vrt->b;
        }
    } else {
      vrt->vertex.insert(std::make_pair(vr, std::make_pair(vrt->a,
      vrt->b)));
    }
  }

size_t DistanceTo(const Vertex &trg) const {
    return vrt->vertex[trg].second;
  }

Vertex Parent(const Vertex &vr) const {
      return vrt->vertex[vr].first;
  }
};

(1 237 b)

0.074s 0.024s 9