fork download
copy 
  1.  
  2. #include <iostream>
  3. #include <vector>
  4. #include <string>
  5. #include <algorithm>
  6. #include <numeric>
  7.  
  8. using namespace std;
  9.  
  10. struct Edge {
  11.     int u, v;           // Indeksy wierzchołków (pól)
  12.     int weight;         // Waga: 0 dla Tui (T), 1 dla Cisu (C)
  13.     int r_out, c_out;   // Współrzędne w mapie wyjściowej
  14.     bool is_cis;        // Czy oryginalnie to był Cis
  15. };
  16. struct DSU {
  17.     vector<int> parent;
  18.     DSU(int n) {
  19.         parent.resize(n);
  20.         iota(parent.begin(), parent.end(), 0);
  21.     }
  22.  
  23.     int find(int i) {
  24.         if (parent[i] == i)
  25.             return i;
  26.         return parent[i] = find(parent[i]);
  27.     }
  28.  
  29.     bool unite(int i, int j) {
  30.         int root_i = find(i);
  31.         int root_j = find(j);
  32.         if (root_i != root_j) {
  33.             parent[root_i] = root_j;
  34.             return true;
  35.         }
  36.         return false;
  37.     }
  38. };
  39.  
  40. bool compareEdges(const Edge& a, const Edge& b) {
  41.     return a.weight < b.weight;
  42. }
  43.  
  44. int main() {
  45.     // Optymalizacja I/O
  46.     ios_base::sync_with_stdio(false);
  47.     cin.tie(NULL);
  48.  
  49.     int m, n;
  50.     if (!(cin >> m >> n)) return 0;
  51.  
  52.     vector<Edge> edges;
  53.     int total_cis_available = 0;
  54.  
  55.     vector<string> result_map; 
  56.     result_map.reserve(2 * m - 1);
  57.  
  58.     for (int i = 0; i < m; ++i) {
  59.         string row;
  60.         cin >> row;
  61.         result_map.push_back(string(n - 1, 'Z')); // Placeholder na mapie
  62.  
  63.         for (int j = 0; j < n - 1; ++j) {
  64.             int u = i * n + j;
  65.             int v = i * n + (j + 1);
  66.             bool is_cis = (row[j] == 'C');
  67.             if (is_cis) total_cis_available++;
  68.  
  69.             // Jeśli to Cis, waga 1 (kosztowne w ścieżce), jeśli Tuja waga 0 (tanie w ścieżce)
  70.             edges.push_back({u, v, is_cis ? 1 : 0, 2 * i, j, is_cis});
  71.         }
  72.     }
  73.  
  74.     // 2. Wczytywanie krawędzi POZIOMYCH (między wierszami i i i+1)
  75.     // Jest ich m-1 wierszy, po n znaków
  76.     for (int i = 0; i < m - 1; ++i) {
  77.         string row;
  78.         cin >> row;
  79.         result_map.insert(result_map.begin() + (2 * i + 1), string(n, 'Z')); // Placeholder
  80.  
  81.         for (int j = 0; j < n; ++j) {
  82.             int u = i * n + j;
  83.             int v = (i + 1) * n + j;
  84.             bool is_cis = (row[j] == 'C');
  85.             if (is_cis) total_cis_available++;
  86.  
  87.             edges.push_back({u, v, is_cis ? 1 : 0, 2 * i + 1, j, is_cis});
  88.         }
  89.     }
  90.  
  91.     // Sortowanie krawędzi: najpierw te o wadze 0 (Tuja), potem 1 (Cis)
  92.     sort(edges.begin(), edges.end(), compareEdges);
  93.  
  94.     DSU dsu(m * n);
  95.     int edges_in_tree = 0;
  96.     int cis_used_in_path = 0;
  97.     int path_edges_count = 0;
  98.  
  99.     // Algorytm Kruskala
  100.     for (const auto& edge : edges) {
  101.         if (dsu.unite(edge.u, edge.v)) {
  102.             // Ta krawędź staje się częścią ścieżki (usuwamy żywopłot)
  103.             result_map[edge.r_out][edge.c_out] = '.'; 
  104.             edges_in_tree++;
  105.  
  106.             if (edge.is_cis) {
  107.                 cis_used_in_path++;
  108.             }
  109.         }
  110.     }
  111.  
  112.     // Obliczenia końcowe
  113.     // Liczba wszystkich możliwych krawędzi wewnątrz
  114.     long long total_edges_count = edges.size();
  115.     // Liczba krawędzi, które zostały żywopłotami = Wszystkie - Te w ścieżce
  116.     long long final_hedges_count = total_edges_count - edges_in_tree;
  117.     // Liczba cisu w żywopłocie = Cały dostępny cis - Cis "zmarnowany" na ścieżkę
  118.     long long final_cis_hedges = total_cis_available - cis_used_in_path;
  119.  
  120.     // Wyjście
  121.     cout << final_hedges_count << " " << final_cis_hedges << "\n";
  122.     for (const auto& row : result_map) {
  123.         cout << row << "\n";
  124.     }
  125.  
  126.     return 0;
  127. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
4 5
CCTT
TTCT
TCTT
TTCT
CCCTT
TCCCT
CTCTT
stdout
copy 
12 10
Z...
.ZZ..
..ZZ
.ZZZ.
.Z.Z
Z....
..Z.
https://ideone.com/xayv60
language:
C++14 (gcc 8.3)
created:
14 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!