Submission #232319

#TimeUsernameProblemLanguageResultExecution timeMemory
232319pedy4000Raspad (COI17_raspad)C++14
26 / 100
534 ms632 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...