oj.uz

답안 #480285

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
480285 2021-10-15T13:44:02 Z BERNARB01 Raspad (COI17_raspad) C++17
26 / 100
 3420 ms 5724 KB 
#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.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3788 KB Output is correct
2 Correct 5 ms 3788 KB Output is correct
3 Correct 4 ms 3788 KB Output is correct
4 Correct 4 ms 3788 KB Output is correct
5 Correct 4 ms 3788 KB Output is correct
6 Correct 5 ms 3788 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3788 KB Output is correct
2 Correct 5 ms 3788 KB Output is correct
3 Correct 4 ms 3788 KB Output is correct
4 Correct 4 ms 3788 KB Output is correct
5 Correct 4 ms 3788 KB Output is correct
6 Correct 5 ms 3788 KB Output is correct
7 Correct 149 ms 4044 KB Output is correct
8 Correct 3 ms 3916 KB Output is correct
9 Correct 427 ms 4084 KB Output is correct
10 Correct 121 ms 4060 KB Output is correct
11 Correct 256 ms 4088 KB Output is correct
12 Correct 73 ms 4044 KB Output is correct
13 Correct 209 ms 4060 KB Output is correct

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3420 ms 5724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 3788 KB Output is correct
2 Correct 5 ms 3788 KB Output is correct
3 Correct 4 ms 3788 KB Output is correct
4 Correct 4 ms 3788 KB Output is correct
5 Correct 4 ms 3788 KB Output is correct
6 Correct 5 ms 3788 KB Output is correct
7 Correct 149 ms 4044 KB Output is correct
8 Correct 3 ms 3916 KB Output is correct
9 Correct 427 ms 4084 KB Output is correct
10 Correct 121 ms 4060 KB Output is correct
11 Correct 256 ms 4088 KB Output is correct
12 Correct 73 ms 4044 KB Output is correct
13 Correct 209 ms 4060 KB Output is correct
14 Incorrect 3420 ms 5724 KB Output isn't correct
15 Halted 0 ms 0 KB -