fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 3e5;
  9.  
  10. int n, k, sz[maxn + 10][2], leader[maxn + 10], ans = 0, dp[maxn + 10];
  11. string s;
  12. vector<int> pos[maxn + 10];
  13.  
  14. int find_leader(int x)
  15. {
  16.     if (x == leader[x])
  17.         return x;
  18.     int root = find_leader(leader[x]);
  19.     dp[x] ^= dp[leader[x]];
  20.     leader[x] = root;
  21.     return root;
  22. }
  23. int get_cost(int x)
  24. {
  25.     x = find_leader(x);
  26.     if (x == k + 1)
  27.         return sz[x][1];
  28.     return min(sz[x][0], sz[x][1]);
  29. }
  30. void connect(int x, int y, int w)
  31. {
  32.     int root_x = find_leader(x);
  33.     int root_y = find_leader(y);
  34.     if (root_x == root_y)
  35.         return ;
  36. //    cerr << x << ' ' << y << ' ' << root_x << ' ' << root_y << '\n';
  37.     w ^= dp[x] ^ dp[y];
  38.     ans -= get_cost(root_x);
  39.     ans -= get_cost(root_y);
  40.     if (root_y == k + 1)
  41.         swap(root_x, root_y);
  42.     leader[root_y] = root_x;
  43.     dp[root_y] = w;
  44.     sz[root_x][0] += sz[root_y][w];
  45.     sz[root_x][1] += sz[root_y][1 ^ w];
  46.     ans += get_cost(root_x);
  47. }
  48.  
  49. int main()
  50. {
  51.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  52.     if (fopen("BAI3.INP", "r"))
  53.     {
  54.         freopen("BAI3.INP", "r", stdin);
  55.         freopen("BAI3.OUT", "w", stdout);
  56.     }
  57.  
  58.     cin >> n >> k;
  59.     cin >> s;
  60.     s = ' ' + s;
  61.     for (int i = 1; i <= k; i++)
  62.     {
  63.         int c;
  64.         cin >> c;
  65.         while(c--)
  66.         {
  67.             int x;
  68.             cin >> x;
  69.             pos[x].push_back(i);
  70.         }
  71.     }
  72.     for (int i = 1; i <= k + 1; i++)
  73.     {
  74.         sz[i][0] = 1;
  75.         sz[i][1] = 0;
  76.         leader[i] = i;
  77.         dp[i] = 0;
  78.     }
  79.     for (int i = 1; i <= n; i++)
  80.     {
  81.         if (pos[i].size())
  82.         {
  83.             int w = 1 ^ (s[i] - '0');
  84.             int x = pos[i].front();
  85.             int y = pos[i].back();
  86.             if (x == y)
  87.                 connect(x, k + 1, w);
  88.             else
  89.                 connect(x, y, w);
  90.         }
  91.         cout << ans, el;
  92.     }
  93. }
  94.  
Success #stdin #stdout 0.01s 13928KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0Onv1K
language:
C++14 (gcc 8.3)
created:
27 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!