fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <numeric>
  5.  
  6. // --- Khai báo biến toàn cục ---
  7. const int MAXN = 300005; // Kích thước tối đa cho các mảng
  8.  
  9. int n, k; // n: số bóng đèn, k: số tập hợp
  10. std::string s; // Chuỗi trạng thái ban đầu của các bóng đèn
  11. std::vector<int> bulb_to_sets[MAXN]; // Mảng vector, lưu các tập hợp mà mỗi bóng đèn thuộc về
  12.  
  13. // --- Các cấu trúc dữ liệu cho Disjoint Set Union (DSU) ---
  14. int parent[MAXN]; // Mảng cha, parent[i] là nút cha của nút i
  15. int val[MAXN];    // val[i] lưu kết quả của (giá trị nút i) XOR (giá trị nút cha của nó)
  16.                   // Đây là trọng số trên cạnh từ i đến parent[i]
  17. int sz[MAXN][2];  // Với mỗi gốc của một thành phần liên thông, lưu kích thước của nó.
  18.                   // sz[root][0]: số nút có giá trị CÙNG với gốc
  19.                   // sz[root][1]: số nút có giá trị KHÁC với gốc
  20. int total_min_ops = 0; // Tổng số thao tác tối thiểu cần thiết
  21.  
  22. // --- Hàm tìm gốc của một tập hợp (Find operation) ---
  23. // Sử dụng kỹ thuật nén đường đi (path compression) và cập nhật trọng số XOR
  24. int find_set(int v) {
  25.     if (v == parent[v]) {
  26.         // Nếu v là gốc, trả về chính nó
  27.         return v;
  28.     }
  29.     // Đệ quy để tìm gốc cuối cùng của chuỗi cha
  30.     int root = find_set(parent[v]);
  31.     // Trong quá trình nén đường đi, cập nhật val[v]
  32.     // val[v] mới = val[v] cũ ^ val[parent[v]] cũ
  33.     val[v] ^= val[parent[v]];
  34.     // Nén đường đi: nối v trực tiếp với gốc
  35.     parent[v] = root;
  36.     return root;
  37. }
  38.  
  39. // --- Hàm tính chi phí cho một thành phần liên thông ---
  40. int get_cost(int v) {
  41.     // Nếu thành phần này đã được nối với nút cơ sở (k+1), giá trị của nó là cố định.
  42.     // Chi phí lúc này chính là số nút phải bật (có giá trị 1).
  43.     // Vì nút gốc (của k+1) có giá trị 0, nên chi phí là số nút có giá trị khác gốc.
  44.     if (find_set(v) == find_set(k + 1)) {
  45.         return sz[v][1];
  46.     }
  47.     // Nếu thành phần là tự do, ta có thể chọn giá trị cho gốc là 0 hoặc 1.
  48.     // Ta chọn phương án tốn ít thao tác hơn.
  49.     return std::min(sz[v][0], sz[v][1]);
  50. }
  51.  
  52. // --- Hàm hợp nhất hai tập hợp (Unite operation) ---
  53. void unite_sets(int u, int v, int w) {
  54.     int root_u = find_set(u);
  55.     int root_v = find_set(v);
  56.  
  57.     // w là ràng buộc yêu cầu: giá trị(u) ^ giá trị(v) = w
  58.     // Sau khi chạy find_set, ta có:
  59.     //   giá trị(u) = giá trị(root_u) ^ val[u]
  60.     //   giá trị(v) = giá trị(root_v) ^ val[v]
  61.     // Thay vào ràng buộc, ta có: giá trị(root_u) ^ giá trị(root_v) = w ^ val[u] ^ val[v]
  62.     int required_xor = w ^ val[u] ^ val[v];
  63.  
  64.     if (root_u != root_v) { // Chỉ hợp nhất nếu chúng chưa cùng một thành phần
  65.         // 1. Trừ đi chi phí của hai thành phần cũ khỏi tổng chi phí
  66.         total_min_ops -= get_cost(root_u);
  67.         total_min_ops -= get_cost(root_v);
  68.  
  69.         // Ưu tiên hợp nhất vào thành phần có chứa nút cơ sở (k+1) nếu có
  70.         if (root_u == find_set(k + 1)) std::swap(root_u, root_v);
  71.  
  72.         // 2. Thực hiện hợp nhất: nối gốc của u vào gốc của v
  73.         parent[root_u] = root_v;
  74.         // Cập nhật trọng số cho cạnh nối mới này
  75.         val[root_u] = required_xor;
  76.  
  77.         // 3. Cập nhật kích thước cho thành phần mới (tại root_v)
  78.         if (required_xor == 0) { // Nếu giá trị(root_u) == giá trị(root_v)
  79.             sz[root_v][0] += sz[root_u][0];
  80.             sz[root_v][1] += sz[root_u][1];
  81.         } else { // Nếu giá trị(root_u) != giá trị(root_v)
  82.             sz[root_v][0] += sz[root_u][1];
  83.             sz[root_v][1] += sz[root_u][0];
  84.         }
  85.  
  86.         // 4. Cộng chi phí của thành phần mới vào tổng chi phí
  87.         total_min_ops += get_cost(root_v);
  88.     }
  89. }
  90.  
  91. int main() {
  92.     // Tăng tốc độ nhập xuất
  93.     std::ios_base::sync_with_stdio(false);
  94.     std::cin.tie(NULL);
  95.  
  96.     // Đọc dữ liệu đầu vào
  97.     std::cin >> n >> k;
  98.     std::cin >> s;
  99.  
  100.     for (int i = 1; i <= k; ++i) {
  101.         int c; // Số lượng đèn trong tập hợp
  102.         std::cin >> c;
  103.         for (int j = 0; j < c; ++j) {
  104.             int x; // Chỉ số của bóng đèn
  105.             std::cin >> x;
  106.             bulb_to_sets[x].push_back(i);
  107.         }
  108.     }
  109.  
  110.     // Khởi tạo DSU cho k tập hợp và 1 nút cơ sở (k+1)
  111.     for (int i = 1; i <= k + 1; ++i) {
  112.         parent[i] = i;      // Ban đầu, mỗi nút là gốc của chính nó
  113.         val[i] = 0;         // Khoảng cách XOR đến cha (chính nó) là 0
  114.         sz[i][0] = 1;       // Thành phần có 1 nút, có giá trị CÙNG gốc
  115.         sz[i][1] = 0;       // Thành phần có 0 nút, có giá trị KHÁC gốc
  116.     }
  117.  
  118.     // Xử lý lần lượt các bóng đèn từ 1 đến n
  119.     for (int i = 1; i <= n; ++i) {
  120.         // target là giá trị XOR cần có để đèn i bật
  121.         // Nếu s[i-1] là '0', cần XOR 1. Nếu là '1', cần XOR 0.
  122.         int target = 1 - (s[i - 1] - '0');
  123.  
  124.         if (bulb_to_sets[i].size() == 1) {
  125.             // Trường hợp 1: Đèn i chỉ thuộc 1 tập hợp A_p
  126.             // Ràng buộc: giá trị(p) = target <=> giá trị(p) ^ giá trị(cơ sở) = target
  127.             int set_idx = bulb_to_sets[i][0];
  128.             unite_sets(set_idx, k + 1, target);
  129.         } else if (bulb_to_sets[i].size() == 2) {
  130.             // Trường hợp 2: Đèn i thuộc 2 tập hợp A_p và A_q
  131.             // Ràng buộc: giá trị(p) ^ giá trị(q) = target
  132.             int set1_idx = bulb_to_sets[i][0];
  133.             int set2_idx = bulb_to_sets[i][1];
  134.             unite_sets(set1_idx, set2_idx, target);
  135.         }
  136.  
  137.         // In ra kết quả cho i đèn đầu tiên
  138.         std::cout << total_min_ops << "\n";
  139.     }
  140.  
  141.     return 0;
  142. }
Success #stdin #stdout 0.01s 14488KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/31KGhR
language:
C++14 (gcc 8.3)
created:
5 days 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!