| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 232319 |
2020-05-16T17:11:49 Z |
pedy4000 |
Raspad (COI17_raspad) |
C++14 |
|
534 ms |
632 KB |
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 1e3 + 3;
int n, m;
ll ans;
int num, cnt;
int par[N * N];
string s[N];
int Arr[N];
int root (int v) {
return (par[v] == v? v: par[v] = root(par[v]));
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> s[i];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
Arr[j] = -1;
num = 0;
cnt = 0;
for (int j = 0; j < m; j++)
if (s[i][j] == '1') {
Arr[j] = num;
par[num] = num;
num++;
cnt++;
}
for (int j = 0; j + 1 < m; j++)
if (s[i][j] == '1' && s[i][j + 1] == '1') {
par[root(Arr[j])] = root(Arr[j + 1]);
cnt--;
}
ans += cnt;
for (int j = i + 1; j < n; j++) {
for (int k = 0; k < m; k++) {
if (s[j][k] == '0')
Arr[k] = -1;
else {
if (Arr[k] == -1) {
Arr[k] = num;
par[num] = num;
num++;
cnt++;
}
}
}
for (int k = 0; k + 1 < m; k++)
if (s[j][k] == '1' && s[j][k + 1] == '1' && root(Arr[k]) != root(Arr[k + 1])) {
par[root(Arr[k])] = root(Arr[k + 1]);
cnt--;
}
ans += cnt;
}
}
cout << ans << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
8 ms |
384 KB |
Output is correct |
| 3 |
Correct |
6 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
7 ms |
384 KB |
Output is correct |
| 6 |
Correct |
7 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
8 ms |
384 KB |
Output is correct |
| 3 |
Correct |
6 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
7 ms |
384 KB |
Output is correct |
| 6 |
Correct |
7 ms |
384 KB |
Output is correct |
| 7 |
Correct |
207 ms |
512 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
534 ms |
632 KB |
Output is correct |
| 10 |
Correct |
43 ms |
384 KB |
Output is correct |
| 11 |
Correct |
330 ms |
632 KB |
Output is correct |
| 12 |
Correct |
47 ms |
504 KB |
Output is correct |
| 13 |
Correct |
250 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
8 ms |
384 KB |
Output is correct |
| 3 |
Correct |
6 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
7 ms |
384 KB |
Output is correct |
| 6 |
Correct |
7 ms |
384 KB |
Output is correct |
| 7 |
Correct |
207 ms |
512 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
534 ms |
632 KB |
Output is correct |
| 10 |
Correct |
43 ms |
384 KB |
Output is correct |
| 11 |
Correct |
330 ms |
632 KB |
Output is correct |
| 12 |
Correct |
47 ms |
504 KB |
Output is correct |
| 13 |
Correct |
250 ms |
512 KB |
Output is correct |
| 14 |
Runtime error |
5 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Halted |
0 ms |
0 KB |
- |
