Naxocist

magnetic

Apr 29th, 2023
654
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.84 KB | Source Code | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. const int N = 1e5 + 3;
  6. int dsu[N];
  7. int n, m, res;
  8.  
  9. int par(int u) {
  10.     return (dsu[u] == u ? u : dsu[u] = par(dsu[u]));
  11. }
  12.  
  13. void un(int u, int v) {
  14.     int x = par(u), y = par(v);
  15.     if(x == y) return ;
  16.     dsu[x] = y; res--;
  17. }
  18.  
  19. int main() {
  20.     ios_base::sync_with_stdio(0); cin.tie(0);
  21.     cin >> n >> m;
  22.     string s; cin >> s;
  23.  
  24.     for(int i=0; i<n; ++i) dsu[i] = i;
  25.     res = n;
  26.     for(int i=0; i<n; ++i) {
  27.         if(s[i] == '1') {
  28.             int k = 1;
  29.             while(k <= m && s[(i+k)%n] != '1') {
  30.                 un(i, (i+k)%n);
  31.                 k++;
  32.             }
  33.             k = 1;
  34.             while(k <= m && s[(i-k+n)%n] != '1') {
  35.                 un(i, (i-k+n)%n);
  36.                 k++;
  37.             }
  38.         }
  39.     }
  40.     printf("%d", res);
  41.  
  42.     return 0;
  43. }
Advertisement
Add Comment
Please, Sign In to add comment