Submission #480285

#	Time	Username	Problem	Language	Result	Execution time	Memory
480285		BERNARB01	Raspad (COI17_raspad)	C++17	26 / 100	3420 ms	5724 KiB

raspad

#include <bits/stdc++.h>

using namespace std;

const int N = (int) 1e5 + 9;

int n, m, pz[N], nCC, dsuN, id[N][50];
string a[N];

inline void init() {
  fill(pz, pz + dsuN, -1);
  nCC = dsuN = 0;
}

inline int fnd(int u) {
  return (pz[u] < 0 ? u : (pz[u] = fnd(pz[u])));
}

inline void unite(int u, int v) {
  u = fnd(u); v = fnd(v);
  if (u != v) {
    if (pz[u] < pz[v]) {
      swap(pz[u], pz[v]);
    }
    pz[v] += pz[u];
    pz[u] = v; nCC -= 1;
  }
}

inline int addNew() {
  nCC += 1;
  pz[dsuN] = -1;
  dsuN += 1;
  return dsuN - 1;
}

inline void add(int r, bool connectToBefore) {
  for (int i = 0; i < m; i++) {
    if (a[r][i] == '1') {
      id[r][i] = addNew();
      if (connectToBefore && a[r - 1][i] == '1') {
        unite(id[r][i], id[r - 1][i]);
      }
      if (i && a[r][i - 1] == '1') {
        unite(id[r][i], id[r][i - 1]);
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  memset(pz, -1, sizeof pz);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  long long ans = 0;
  for (int s = 0; s < n; s++) {
    init();
    for (int e = s; e < n; e++) {
      add(e, (e > s));
      ans += nCC;
    }
  }
  cout << ans << '\n';
  return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 17 / 17
• Subtask 3: 0 / 35
• Subtask 4: 0 / 39