SHARE
TWEET

Untitled

a guest Dec 7th, 2019 85 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <assert.h>
  3. #include <chrono>
  4. #include <iostream>
  5. #include <limits>
  6. #include <random>
  7. #include <vector>
  8. #include <string>
  9. #include <utility>
  10. #include <queue>
  11. #include <unordered_map>
  12. #include <cmath>
  13. #include <unordered_set>
  14. #include <set>
  15. #include <list>
  16. #include <functional>
  17.  
  18. template <class T>
  19. class TimeMeasure {
  20. public:
  21.     TimeMeasure () {
  22.         point_ = std::chrono::steady_clock::now();
  23.     }
  24.     int GetTime() {
  25.         std::chrono::steady_clock::time_point current = std::chrono::steady_clock::now();
  26.         int result = std::chrono::duration_cast<T>(current - point_).count();
  27.         point_ = std::chrono::steady_clock::now();
  28.         return result;
  29.     }
  30.     void SetLast() {
  31.         point_ = std::chrono::steady_clock::now();
  32.     }
  33. private:
  34.     std::chrono::steady_clock::time_point point_;
  35. };
  36.  
  37. struct Querry {
  38.     int from = -1;
  39.     int to = -1;
  40. };
  41.  
  42. template<typename T>
  43. std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
  44.     os << "{";
  45.     for (const auto& item : vec) {
  46.         os << item << " ";
  47.     }
  48.     os << "}";
  49.     return os;
  50. }
  51.  
  52. template<typename T>
  53. std::ostream& operator<<(std::ostream& os, const std::unordered_set<T>& vec) {
  54.     os << "{";
  55.     for (const auto& item : vec) {
  56.         os << item << " ";
  57.     }
  58.     os << "}";
  59.     return os;
  60. }
  61.  
  62. template<typename T, typename Q>
  63. std::ostream& operator<<(std::ostream& os, const std::pair<T, Q>& item) {
  64.     os << "[" << item.first << " " << item.second << "] ";
  65.     return os;
  66. }
  67.  
  68. std::vector<int> GenRandomArray(std::mt19937 *gen, int count, int from, int to) {
  69.     std::uniform_int_distribution<int> dist(from, to);
  70.     std::vector<int> data(count);
  71.     for (auto& cur : data) {
  72.         cur = dist(*gen);
  73.     }
  74.     return data;
  75. }
  76.  
  77.  
  78. struct Edge {
  79.     int from = -1;
  80.     int to = -1;
  81.     int weight;
  82. };
  83.  
  84. std::ostream& operator<<(std::ostream& stream, const Edge& edge) {
  85.     stream << "[ " << edge.from << ", " << edge.to << ", " << edge.weight << "] ";
  86.     return stream;
  87. }
  88.  
  89. struct pair_hash
  90. {
  91.     template <class P, class Q>
  92.     std::size_t operator() (const std::pair<P, Q> &pair) const
  93.     {
  94.         return std::hash<P>()(pair.first) ^ std::hash<Q>()(pair.second);
  95.     }
  96. };
  97.  
  98. std::vector<Edge> GenerateRandomGraph(std::mt19937 *gen,
  99.                                       size_t graph_size,
  100.                                       size_t edges_number, bool random_weight = false) {
  101.     std::uniform_int_distribution<int> dist(0, graph_size - 1);
  102.     std::uniform_int_distribution<int> dist_weight(0, 2);
  103.  
  104.     std::unordered_set<std::pair<int, int>, pair_hash> edges;
  105.     std::vector<Edge> result;
  106.     while (result.size() < edges_number) {
  107.         auto pair = std::make_pair(dist(*gen), dist(*gen));
  108.         if (pair.first == pair.second) {
  109.             continue;
  110.         }
  111.         //        auto pair_second = std::make_pair(pair.second, pair.first);
  112.         //        if (edges.count(pair) == 0 && edges.count(pair_second) == 0) {
  113.         edges.insert(pair);
  114.  
  115.         result.push_back({pair.first + 1, pair.second + 1, 1000});
  116.         if (random_weight) {
  117.             result.back().weight = dist_weight(*gen);
  118.         }
  119.         //        }
  120.     }
  121.     return result;
  122. }
  123.  
  124. std::vector<Edge> GenerateCycleGraph(std::mt19937 *gen,
  125.                                      size_t graph_size, int number_of_cycles, int cycle_length,
  126.                                      bool positive, std::unordered_set<int>& used_vertexes) {
  127.     if (number_of_cycles * cycle_length + used_vertexes.size() > graph_size) {
  128.         throw std::domain_error("WRONG PARAMS");
  129.     }
  130.     std::uniform_int_distribution<int> dist(0, graph_size - 1);
  131.  
  132.     std::vector<Edge> result;
  133.     for (int cycle_num = 1; cycle_num <= number_of_cycles; ++cycle_num) {
  134.         int starting_vertex;
  135.  
  136.         auto vert = dist(*gen);
  137.         while (used_vertexes.count(vert) == 1) {
  138.             vert = dist(*gen);
  139.         }
  140.  
  141.         starting_vertex = vert;
  142.  
  143.         int last_vertex = starting_vertex;
  144.         used_vertexes.insert(last_vertex);
  145.  
  146.         for (int index = 1; index < cycle_length; ++index) {
  147.             auto vert = dist(*gen);
  148.             while (used_vertexes.count(vert) == 1) {
  149.                 vert = dist(*gen);
  150.             }
  151.  
  152.             result.push_back({last_vertex + 1, vert + 1, 1});
  153.             last_vertex = vert;
  154.             used_vertexes.insert(last_vertex);
  155.         }
  156.  
  157.         if (positive) {
  158.             result.push_back({last_vertex + 1, starting_vertex + 1, 1});
  159.         } else {
  160.             result.push_back({last_vertex + 1, starting_vertex + 1, -cycle_length});
  161.         }
  162.     }
  163.     return result;
  164. }
  165.  
  166. void Floyd(int vertex_number, const std::vector<Edge>& edges,
  167.            std::vector<std::vector<int>>& distances) {
  168.  
  169.     for (const auto& edge: edges) {
  170.         distances.at(edge.from - 1).at(edge.to - 1) =
  171.                 std::min(distances.at(edge.from - 1).at(edge.to - 1), edge.weight);
  172.     }
  173.     for (int i = 0; i < vertex_number; ++i) {
  174.         distances.at(i).at(i) = 0;
  175.     }
  176.  
  177.     for (int index_k = 0; index_k < vertex_number; ++index_k) {
  178.         for (int index_i = 0; index_i < vertex_number; ++index_i) {
  179.             for (int index_j = 0; index_j < vertex_number; ++index_j) {
  180.                 if (distances.at(index_i).at(index_k) == std::numeric_limits<int>::max()) {
  181.                     continue;
  182.                 }
  183.                 if (distances.at(index_k).at(index_j) == std::numeric_limits<int>::max()) {
  184.                     continue;
  185.                 }
  186.                 auto sum = distances.at(index_i).at(index_k) +
  187.                         distances.at(index_k).at(index_j);
  188.                 if (distances.at(index_i).at(index_j) > sum) {
  189.                     distances.at(index_i).at(index_j) = sum;
  190.                 }
  191.             }
  192.         }
  193.     }
  194. }
  195.  
  196. int BellmanFord(int vertex_number, std::vector<Edge>& edges) {
  197.     //    std::cout<<edges<<std::endl;
  198.     std::vector<int> distance(vertex_number + 1, std::numeric_limits<int>::max());
  199.     std::vector<int> parent(vertex_number + 1, -1);
  200.     for (int i = 1; i <=vertex_number; ++i) {
  201.         edges.push_back({vertex_number + 1, i, 1});
  202.     }
  203.     //    std::cout<<edges<<std::endl;
  204.  
  205.  
  206.     distance.at(vertex_number) = 0;
  207.  
  208.     for (int index = 0; index < vertex_number; ++index) {
  209.  
  210.         for (const auto& edge : edges) {
  211.             if (distance.at(edge.from - 1) == std::numeric_limits<int>::max()) {
  212.                 continue;
  213.             }
  214.             if (distance.at(edge.from - 1) + edge.weight < distance.at(edge.to - 1)) {
  215.                 distance.at(edge.to - 1) = distance.at(edge.from - 1) + edge.weight;
  216.                 parent.at(edge.to - 1) = edge.from - 1;
  217.             }
  218.         }
  219.     }
  220.  
  221.     std::unordered_set<int> problem_vertex;
  222.     for (const auto& edge : edges) {
  223.         if (distance.at(edge.from - 1) + edge.weight < distance.at(edge.to - 1)) {
  224.             problem_vertex.insert(edge.from - 1);
  225.             //            std::cout << " NEGATIVE LOOP " << std::endl;
  226.         }
  227.     }
  228.  
  229.     //    std::cout<<":LK:LK  "<<std::endl;
  230.     int result = std::numeric_limits<int>::max();
  231.     for (auto id : problem_vertex) {
  232.         //        std::cout<<edges<<std::endl;
  233.         //        std::cout<<problem_vertex<<std::endl;
  234.         //        std::cout<<parent<<std::endl;
  235.         {
  236.             std::unordered_set<int> path;
  237.             auto current = id;
  238.             path.insert(current);
  239.             while (parent.at(current) != vertex_number && parent.at(current) != -1 &&
  240.                    path.count(parent.at(current)) == 0) {
  241.                 current = parent.at(current);
  242.                 //                std::cout << "K:ffLK: "<< current<<std::endl;
  243.                 path.insert(current);
  244.             }
  245.             //            std::cout<<":LK "<<std::endl;
  246.             id = current;
  247.             //            id = parent.at(current);
  248.         }
  249.         auto current = id;
  250.         if (current == -1) {
  251.             //            continue;
  252.         }
  253.         //        std::cout<<":LK:L  "<< current <<std::endl;
  254.         //        std::vector<int> path;
  255.         //        path.push_back(current);
  256.  
  257.         if (current < result) {
  258.             result = current;
  259.         }
  260.         while (id != parent.at(current) && current != parent.at(current) &&
  261.                -1 != parent.at(current)) {
  262.             //            std::cout<<id<<" "<<current<<" "<<parent.at(current)<<std::endl;
  263.             current = parent.at(current);
  264.             //            path.push_back(current);
  265.             if (current < result) {
  266.                 result = current;
  267.             }
  268.         }
  269.         //        std::cout<<path<<std::endl;
  270.     }
  271.     //    std::cout << result << std::endl;
  272.     //    std::cout<<problem_vertex<<std::endl;
  273.  
  274.     //    std::cout<<":LK:LK 2  "<<std::endl;
  275.  
  276.     if (result == std::numeric_limits<int>::max()) {
  277.         return -1;
  278.     }
  279.     return result + 1;
  280. }
  281.  
  282. std::vector<int> SolveSimple(int vertex_number, const std::vector<Edge>& edges,
  283.                              const std::vector<Querry>& querries) {
  284.     std::vector<std::vector<int>> distances(vertex_number,
  285.                                             std::vector<int>(vertex_number,
  286.                                                              std::numeric_limits<int>::max()));
  287.     Floyd(vertex_number, edges, distances);
  288.  
  289.     std::vector<int> result(querries.size());
  290.     for (size_t i = 0; i < querries.size(); ++i) {
  291.         result[i] = distances.at(querries.at(i).from - 1).at(querries.at(i).to - 1);
  292.         if (result[i] == std::numeric_limits<int>::max()) {
  293.             result[i] = -1;
  294.         }
  295.     }
  296.     return result;
  297. }
  298.  
  299. class Graph {
  300. public:
  301.     explicit Graph(int vertex_number) : vertex_number_(vertex_number),
  302.                                edges_(vertex_number) {
  303.     }
  304.  
  305.     void AddEdge(int from, int to, int weight) {
  306.         edges_[from].push_back(std::make_pair(to, weight));
  307.     }
  308.  
  309.     std::vector<int> Dijkstra(int src, const std::vector<Querry>& querries,
  310.                                          const std::vector<int>& querry_ind) {
  311.         std::priority_queue<std::pair<int, int>,
  312.                 std::vector<std::pair<int, int>>,
  313.                 std::greater<std::pair<int, int>>> heap;
  314.         std::vector<int> distances(vertex_number_, std::numeric_limits<int>::max());
  315.  
  316.         heap.push(std::make_pair(0, src));
  317.         distances[src] = 0;
  318.         std::unordered_set<int> to_set;
  319.         for (const auto& ind : querry_ind) {
  320.             to_set.insert(querries.at(ind).to - 1);
  321.         }
  322.  
  323.         while (!heap.empty())
  324.         {
  325.             int u_vertex = heap.top().second;
  326.             to_set.erase(u_vertex);
  327.             heap.pop();
  328.             if (to_set.empty()) {
  329.                 break;
  330.             }
  331.  
  332.             for (auto it = edges_[u_vertex].begin(); it != edges_[u_vertex].end(); ++it) {
  333.                 auto dist = distances[u_vertex] + it->second;
  334.                 if (distances[it->first] > dist)
  335.                 {
  336.                     distances[it->first] = dist;
  337.                     heap.push(std::make_pair(distances[it->first], it->first));
  338.                 }
  339.             }
  340.         }
  341.  
  342.         return distances;
  343.     }
  344.  
  345. private:
  346.     int vertex_number_;
  347.     std::vector<std::vector<std::pair<int, int>>> edges_;
  348. };
  349.  
  350. template <class T>
  351. class Heap {
  352. public:
  353.     explicit Heap(bool min_or_max) : min_or_max_(min_or_max) {
  354.     }
  355.  
  356.     void Add(const T& value) {
  357.         auto position = values_.size();
  358.         values_.push_back(value);
  359.         auto current_position = SiftUpStep(position);
  360.         while (position != current_position) {
  361.             position = current_position;
  362.             current_position = SiftUpStep(current_position);
  363.         }
  364.     }
  365.  
  366.     T ExtractMin() {
  367.         auto result = values_.at(0);
  368.         DeleteByPosition(0);
  369.         return result;
  370.     }
  371.  
  372.     const T& GetTop() const {
  373.         assert(!values_.empty());
  374.         return values_.front();
  375.     }
  376.  
  377.     bool Empty() const {
  378.         return values_.empty();
  379.     }
  380.  
  381.     size_t GetSize() const {
  382.         return values_.size();
  383.     }
  384.  
  385.     void DecreasePriority(const T& item) {
  386.         bool found = false;
  387.         for (size_t ind = 0; ind < values_.size(); ++ind) {
  388.             if (values_[ind].key == item.key) {
  389.                 values_[ind].priority = item.priority;
  390.                 auto position = ind;
  391.                 auto current_position = SiftUpStep(position);
  392.                 while (position != current_position) {
  393.                     position = current_position;
  394.                     current_position = SiftUpStep(current_position);
  395.                 }
  396.                 found = true;
  397.                 break;
  398.             }
  399.         }
  400.  
  401.         if (!found) {
  402.             Add(item);
  403.         }
  404.     }
  405.  
  406.     const auto& GetValues() const {
  407.         return values_;
  408.     }
  409.  
  410. private:
  411.     bool min_or_max_;
  412.     const size_t heap_arity_ = 2;
  413.     std::vector<T> values_;
  414.     std::vector<T> deleted_values_;
  415.  
  416.     inline bool compare_(const T& lhs, const T& rhs) const {
  417.         if (min_or_max_) {
  418.             return lhs.priority > rhs.priority;
  419.         } else {
  420.             return lhs.priority < rhs.priority;
  421.         }
  422.     }
  423.  
  424.     void DeleteByPosition(size_t position) {
  425.         if (position + 1 == values_.size()) {
  426.             values_.pop_back();
  427.             return;
  428.         }
  429.         values_.at(position) = values_.back();
  430.         values_.pop_back();
  431.  
  432.         auto current_position = SiftUpStep(position);
  433.         while (position != current_position) {
  434.             position = current_position;
  435.             current_position = SiftUpStep(current_position);
  436.         }
  437.  
  438.         current_position = SiftDownStep(position);
  439.         while (position != SiftDownStep(position)) {
  440.             position = current_position;
  441.             current_position = SiftDownStep(current_position);
  442.         }
  443.     }
  444.  
  445.     size_t SiftUpStep(size_t position) {
  446.         if (position == 0) {
  447.             return position;
  448.         } else {
  449.             auto parent = GetParent(position);
  450.             if (compare_(values_.at(position), values_.at(parent))) {
  451.                 std::swap(values_.at(position), values_.at(parent));
  452.                 return parent;
  453.             } else {
  454.                 return position;
  455.             }
  456.         }
  457.     }
  458.  
  459.     size_t SiftDownStep(size_t position) {
  460.         auto child = GetBestChild(position);
  461.         if (child != std::numeric_limits<size_t>::max()) {
  462.             if (compare_(values_.at(child), values_.at(position))) {
  463.                 std::swap(values_.at(child), values_.at(position));
  464.             }
  465.             return child;
  466.         } else {
  467.             return position;
  468.         }
  469.     }
  470.  
  471.     size_t GetBestChild(size_t position) const {
  472.         size_t result = std::numeric_limits<size_t>::max();
  473.         for (size_t i = 0; i < heap_arity_; ++i) {
  474.             auto child_ind = GetKthChild(position, i);
  475.             if (child_ind < values_.size()) {
  476.                 if (i == 0) {
  477.                     result = child_ind;
  478.                 } else {
  479.                     if (compare_(values_.at(child_ind), values_.at(result))) {
  480.                         result = child_ind;
  481.                     }
  482.                 }
  483.             }
  484.         }
  485.         return result;
  486.     }
  487.     size_t GetParent(size_t ind) const {
  488.         return (ind - 1) / heap_arity_;
  489.     }
  490.  
  491.     size_t GetKthChild(size_t ind, size_t k_num) const {
  492.         assert(k_num < heap_arity_);
  493.         return  heap_arity_ * ind + k_num + 1;
  494.     }
  495. };
  496.  
  497. struct HeapItem {
  498.     int key = -1;
  499.     int priority = -1;
  500. };
  501.  
  502. template <class T>
  503. std::ostream& operator<<(std::ostream& os, const Heap<T>& heap) {
  504.     for (const auto& item : heap.GetValues()) {
  505.         os << item << " | ";
  506.     }
  507.     return os;
  508. }
  509.  
  510. std::ostream& operator<<(std::ostream& os, const HeapItem& item) {
  511.     os << "[" << item.key << ", " << item.priority << "]";
  512.     return os;
  513. }
  514.  
  515. bool operator==(const HeapItem& lhs, const HeapItem& rhs) {
  516.     return lhs.key == rhs.key && lhs.priority == rhs.priority;
  517. }
  518.  
  519. class PriorityQueue {
  520. public:
  521.     void AddItem (const HeapItem& item) {
  522.         //        std::cout<<":LK:dfdL  "<<item.key<<" "<<item.priority<<std::endl;
  523.  
  524.         values_.push_back(item);
  525.     }
  526.  
  527.     HeapItem ExtractMin() {
  528.         assert(!values_.empty());
  529.         //        std::cout<<"VALS "<<values_<<std::endl;
  530.         int lowest_proirity = values_.front().priority;
  531.         HeapItem result = values_.front();
  532.         for (const auto& item : values_) {
  533.             if (item.priority < lowest_proirity) {
  534.                 lowest_proirity = item.priority;
  535.                 result = item;
  536.             }
  537.         }
  538.         //        assert(lowest_proirity != std::numeric_limits<int>::max());
  539.         //        std::cout<<":LK:L  "<<result.key<<" "<<result.priority<<std::endl;
  540.         //        std::cout<<"LKL "<<values_.size()<<std::endl;
  541.         auto it = std::find(values_.begin(), values_.end(), result);
  542.         assert(it != values_.end());
  543.  
  544.         //        std::cout<<":LK:L  "<<it - values_.begin()<<std::endl;
  545.         values_.erase(it);
  546.         //        std::cout<<"LKL0 "<<values_.size()<<std::endl;
  547.  
  548.         return result;
  549.     }
  550.  
  551.     void DecreasePriority(const HeapItem& item) {
  552.         for (auto& val : values_) {
  553.             if (item.key == val.key) {
  554.                 val.priority = item.priority;
  555.             }
  556.         }
  557.     }
  558.  
  559.     bool Empty() const {
  560.         return values_.empty();
  561.     }
  562.  
  563. private:
  564.     std::vector<HeapItem> values_;
  565. };
  566.  
  567. std::vector<int> Dijkstra(int vertex_number, int source,
  568.                           const std::vector<std::vector<Edge>>& edges) {
  569.     //    std::cout<<":LK:LK :1"<<std::endl;
  570.     //    PriorityQueue queue;
  571.     Heap<HeapItem> heap(false);
  572.     std::vector<int> distances(vertex_number, std::numeric_limits<int>::max());
  573.     distances.at(source) = 0;
  574.  
  575.     heap.Add({source, 0});
  576.     for (int i = 0; i < vertex_number; ++i) {
  577.         //        queue.AddItem({i, distances.at(i)});
  578.         //        heap.Add({i, distances.at(i)});
  579.     }
  580.     //    std::cout<<":LK:LK :10"<<std::endl;
  581.  
  582.     std::unordered_set<int> all_vertices;
  583.     while (!heap.Empty()) {
  584.         auto item = heap.ExtractMin();
  585.         for (const auto& neighbor : edges.at(item.key)) {
  586.             if (item.priority == std::numeric_limits<int>::max()) {
  587.                 continue;
  588.             }
  589.             int current_dist = item.priority + neighbor.weight;
  590.             if (current_dist < distances.at(neighbor.to - 1)) {
  591.                 distances.at(neighbor.to - 1) = current_dist;
  592.                 heap.DecreasePriority({neighbor.to - 1, current_dist});
  593.             }
  594.         }
  595.     }
  596.     return distances;
  597. }
  598.  
  599. std::vector<int> Solve(int vertex_number, const std::vector<Edge>& edges,
  600.                        const std::vector<Querry>& querries) {
  601.     Graph graph(vertex_number);
  602.     for (const auto& item : edges) {
  603.         graph.AddEdge(item.from - 1, item.to - 1, item.weight);
  604.     }
  605.     std::vector<std::vector<int>> querries_sorted(vertex_number);
  606.     for (size_t i = 0; i < querries.size(); ++i) {
  607.         querries_sorted.at(querries.at(i).from - 1).push_back(i);
  608.     }
  609.  
  610.     std::vector<int> result_second(querries.size());
  611.     uint64_t total_time = 0;
  612.     for (int i = 0; i < vertex_number; ++i) {
  613.         auto row = graph.Dijkstra(i, querries, querries_sorted.at(i));
  614.         for (const auto& ind : querries_sorted.at(i)) {
  615.             if (row.at(querries.at(ind).to - 1) == std::numeric_limits<int>::max()) {
  616.                 result_second[ind] = -1;
  617.             } else {
  618.                 result_second[ind] = row.at(querries.at(ind).to - 1);
  619.             }
  620.         }
  621.     }
  622.     total_time/=1000;
  623.     //    std::cout<<":LK:LK:L  "<<total_time<<std::endl;
  624.     return result_second;
  625. }
  626.  
  627.  
  628. std::vector<int> SolveThi(int vertex_number, const std::vector<Edge>& edges,
  629.                           const std::vector<Querry>& querries) {
  630.  
  631.     std::vector<std::vector<Edge>> edges_sorted(vertex_number);
  632.     for (const auto& item : edges) {
  633.         edges_sorted.at(item.from - 1).push_back(item);
  634.     }
  635.     std::vector<std::vector<int>> querries_sorted(vertex_number);
  636.     for (size_t i = 0; i < querries.size(); ++i) {
  637.         querries_sorted.at(querries.at(i).from - 1).push_back(i);
  638.     }
  639.  
  640.     std::vector<int> result_second(querries.size());
  641.     uint64_t total_time = 0;
  642.     for (int i = 0; i < vertex_number; ++i) {
  643.         auto row = Dijkstra(vertex_number, i, edges_sorted);
  644.         for (const auto& ind : querries_sorted.at(i)) {
  645.             if (row.at(querries.at(ind).to - 1) == std::numeric_limits<int>::max()) {
  646.                 result_second[ind] = -1;
  647.             } else {
  648.                 result_second[ind] = row.at(querries.at(ind).to - 1);
  649.             }
  650.         }
  651.     }
  652.     total_time/=1000;
  653.     //    std::cout<<":LK:LK:L  "<<total_time<<std::endl;
  654.     return result_second;
  655. }
  656.  
  657. void StressTest() {
  658.     {
  659.         std::mt19937 generator(72874);
  660.  
  661.         for (size_t loop_index = 0; loop_index < 10000; ++loop_index) {
  662.             //            std::cout<<loop_index<<std::endl;
  663.             int vertex_number = 20;
  664.             auto edges = GenerateRandomGraph(&generator, vertex_number,
  665.                                              2 * vertex_number, true);
  666.             int querry_size = 100;
  667.             auto from = GenRandomArray(&generator, querry_size, 1, vertex_number);
  668.             auto to = GenRandomArray(&generator, querry_size, 1, vertex_number);
  669.  
  670.             std::vector<Querry> querries(querry_size);
  671.             for (int i = 0; i < querry_size; ++i) {
  672.                 querries[i].from = from.at(i);
  673.                 querries[i].to = to.at(i);
  674.             }
  675.  
  676.             auto result = Solve(vertex_number, edges, querries);
  677.             auto true_result = SolveSimple(vertex_number, edges, querries);
  678.             if (true_result != result) {
  679.                 throw std::runtime_error("Stress test failed");
  680.             }
  681.         }
  682.  
  683.         std::cout << "STRESS TEST OK" << std::endl;
  684.     }
  685. }
  686.  
  687. void SpeedTest() {
  688.     {
  689.         std::mt19937 generator(72874);
  690.  
  691.         for (size_t loop_index = 0; loop_index < 100; ++loop_index) {
  692.             int vertex_number = 2000;
  693.             auto edges = GenerateRandomGraph(&generator, vertex_number, 20000, true);
  694.             int querry_size = 10000;
  695.             auto from = GenRandomArray(&generator, querry_size, 1, vertex_number);
  696.             auto to = GenRandomArray(&generator, querry_size, 1, vertex_number);
  697.  
  698.             std::vector<Querry> querries(querry_size);
  699.             for (int i = 0; i < querry_size; ++i) {
  700.                 querries[i].from = from.at(i);
  701.                 querries[i].to = to.at(i);
  702.             }
  703.  
  704.             TimeMeasure<std::chrono::milliseconds> timer;
  705.             Solve(vertex_number, edges, querries);
  706.  
  707.             std::cout << "TIME DIFF " << timer.GetTime() << std::endl;
  708.         }
  709.     }
  710. }
  711.  
  712. void TestSolution() {
  713.     {
  714.         int vertex_number = 1;
  715.         std::vector<Edge> edges;
  716.         edges.push_back({1, 1, 1});
  717.         std::vector<Querry> querry;
  718.         querry.push_back({1, 1});
  719.         auto result = Solve(vertex_number, edges, querry);
  720.         std::vector<int> true_result;
  721.         true_result.push_back(0);
  722.         if (result != true_result) {
  723.             throw std::runtime_error("TEST FAILED 1");
  724.         }
  725.     }
  726.  
  727.     {
  728.         int vertex_number = 5;
  729.         std::vector<Edge> edges;
  730.         edges.push_back({1, 2, 2});
  731.         edges.push_back({2, 3, 0});
  732.         edges.push_back({2, 4, 2});
  733.         edges.push_back({3, 4, 1});
  734.  
  735.         std::vector<Querry> querry;
  736.         querry.push_back({1, 4});
  737.         querry.push_back({2, 5});
  738.  
  739.         auto result = Solve(vertex_number, edges, querry);
  740.         std::vector<int> true_result;
  741.         true_result.push_back(3);
  742.         true_result.push_back(-1);
  743.  
  744.         if (result != true_result) {
  745.             throw std::runtime_error("TEST FAILED 2");
  746.         }
  747.     }
  748.  
  749.     std::cout << "TESTS OK " << std::endl;
  750. }
  751.  
  752. int main() {
  753.     TestSolution();
  754.     StressTest();
  755.     SpeedTest();
  756.     return 0;
  757.     std::ios_base::sync_with_stdio(false);
  758.     std::cin.tie(nullptr);
  759.     int vertex_number;
  760.     int edge_number;
  761.     std::cin >> vertex_number >> edge_number;
  762.     std::vector<Edge> edges(edge_number);
  763.     for (auto& edge : edges) {
  764.         std::cin >> edge.from >> edge.to >> edge.weight;
  765.     }
  766.     int querry_number;
  767.     std::cin >> querry_number;
  768.     std::vector<Querry> querries(querry_number);
  769.     for (auto& item : querries) {
  770.         std::cin >> item.from >> item.to;
  771.     }
  772.     auto result = Solve(vertex_number, edges, querries);
  773.     for (const auto& item : result) {
  774.         std::cout << item << "\n";
  775.     }
  776. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top