mrlantan

Untitled

Nov 22nd, 2020
578
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <chrono>
  2. #include <iostream>
  3. #include <vector>
  4. #include <set>
  5. #include <unordered_set>
  6.  
  7. int GetTimeMilliseconds(const std::chrono::steady_clock::time_point& start_time,
  8.                         const std::chrono::steady_clock::time_point& end_time) {
  9.     return std::chrono::duration_cast<std::chrono::milliseconds>(end_time - start_time).count();
  10. }
  11.  
  12. std::pair<std::vector<int>, bool> TryFindColoring(std::vector<std::vector<int>>& g,
  13.                                                   std::vector<int>& colors,
  14.                                                   std::vector<std::unordered_set<int>>& possible_colors,
  15.                                                   std::set<std::pair<int, int>>& possible_colors_sizes,
  16.                                                   const std::chrono::steady_clock::time_point& start_time,
  17.                                                   int& function_calls,
  18.                                                   bool& time_is_up) {
  19.  
  20.     if (possible_colors_sizes.empty()) {
  21.         return { colors, true };
  22.     }
  23.  
  24.     if (function_calls % 10000 == 0) {
  25.         auto cur_time = std::chrono::steady_clock::now();
  26.         auto time_diff = GetTimeMilliseconds(start_time, cur_time);
  27.  
  28.         if (time_diff > 3000) {
  29.             time_is_up = true;
  30.             return {{}, false};
  31.         }
  32.     }
  33.  
  34.     if (possible_colors_sizes.begin()->first == 0) {
  35.         return { {}, false };
  36.     }
  37.  
  38.     auto best_value = *possible_colors_sizes.begin();
  39.     auto best_index = best_value.second;
  40.     possible_colors_sizes.erase(possible_colors_sizes.begin());
  41.  
  42.     auto best_possible_colors = possible_colors[best_index];
  43.     possible_colors[best_index].clear();
  44.  
  45.     for (auto possible_color : best_possible_colors) {
  46.         colors[best_index] = possible_color;
  47.  
  48.         std::vector<int> affected_vertices;
  49.  
  50.         for (auto to : g[best_index]) {
  51.             auto it = possible_colors[to].find(possible_color);
  52.             if (it != possible_colors[to].end()) {
  53.                 affected_vertices.push_back(to);
  54.                 possible_colors_sizes.erase({possible_colors[to].size(), to});
  55.                 possible_colors[to].erase(it);
  56.                 possible_colors_sizes.insert({possible_colors[to].size(), to});
  57.             }
  58.         }
  59.  
  60.         ++function_calls;
  61.         auto result = TryFindColoring(g, colors, possible_colors, possible_colors_sizes,
  62.                                       start_time, function_calls, time_is_up);
  63.  
  64.         if (result.second) {
  65.             return result;
  66.         }
  67.  
  68.         if (time_is_up) {
  69.             return result;
  70.         }
  71.  
  72.         colors[best_index] = 0;
  73.  
  74.         for (auto vertex : affected_vertices) {
  75.             possible_colors_sizes.erase({possible_colors[vertex].size(), vertex});
  76.             possible_colors[vertex].insert(possible_color);
  77.             possible_colors_sizes.insert({possible_colors[vertex].size(), vertex});
  78.         }
  79.     }
  80.  
  81.     possible_colors_sizes.insert(best_value);
  82.     possible_colors[best_index] = best_possible_colors;
  83.  
  84.     return {{}, false};
  85. }
  86.  
  87. auto GeneratePossibleColors(std::vector<std::vector<int>>& g, const std::vector<int>& colors, int max_color) {
  88.     std::vector<std::unordered_set<int> > possible_colors(colors.size());
  89.     std::set<std::pair<int, int>> possible_colors_sizes;
  90.  
  91.     for (int i = 0; i < colors.size(); ++i) {
  92.         if (colors[i] == 0) {
  93.             for (int j = 1; j <= max_color; ++j) {
  94.                 possible_colors[i].insert(j);
  95.             }
  96.  
  97.             for (auto to : g[i]) {
  98.                 if (colors[to] != 0) {
  99.                     possible_colors[i].erase(colors[to]);
  100.                 }
  101.             }
  102.  
  103.             possible_colors_sizes.insert({possible_colors[i].size(), i});
  104.         }
  105.     }
  106.  
  107.     return std::make_pair(possible_colors, possible_colors_sizes);
  108. }
  109.  
  110. void SolveBruteforce(std::istream& is, std::ostream& os) {
  111.     std::vector<std::vector<int>> g;
  112.  
  113.     int n, m;
  114.     is >> n >> m;
  115.  
  116.     g.resize(n);
  117.     std::vector<int> colors(n);
  118.     std::vector<std::set<int>> possible_colors(n);
  119.  
  120.     for (int i = 0; i < m; ++i) {
  121.         int x, y;
  122.         is >> x >> y;
  123.         x--, y--;
  124.         g[x].push_back(y);
  125.         g[y].push_back(x);
  126.     }
  127.  
  128.     int max_color = 0;
  129.  
  130.     for (int i = 0; i < n; ++i) {
  131.         is >> colors[i];
  132.         max_color = std::max(max_color, colors[i]);
  133.     }
  134.  
  135.     int l = max_color - 1;
  136.     int r = n + 1;
  137.  
  138.     auto min_number_colors = n + 1;
  139.     std::vector<int> min_coloring = {};
  140.  
  141.     while(r - l > 1) {
  142.         int mid = (r + l) / 2;
  143.         std::vector<int> colors_copy = colors;
  144.         auto possible_colors_data = GeneratePossibleColors(g, colors_copy, mid);
  145.         auto start_time = std::chrono::steady_clock::now();
  146.         int function_calls = 1;
  147.         bool time_is_up = false;
  148.  
  149.         auto result = TryFindColoring(g,
  150.                                       colors_copy,
  151.                                       possible_colors_data.first,
  152.                                       possible_colors_data.second,
  153.                                       start_time,
  154.                                       function_calls,
  155.                                       time_is_up);
  156.  
  157.         if (result.second) {
  158.             if (mid < min_number_colors) {
  159.                 min_number_colors = mid ;
  160.                 min_coloring = result.first;
  161.             }
  162.             r = mid;
  163.         } else {
  164.             l = mid;
  165.         }
  166.     }
  167.  
  168.     os << min_number_colors - max_color << std::endl;
  169.     for (auto color : min_coloring) {
  170.         os << color << " ";
  171.     }
  172.     os << std::endl;
  173. }
  174.  
  175.  
  176. int main() {
  177.     std::ios_base::sync_with_stdio(false);
  178.     std::cin.tie(nullptr);
  179.  
  180.     SolveBruteforce(std::cin, std::cout);
  181.  
  182.     return 0;
  183. }
  184.  
RAW Paste Data