Submission #232319

#	Time	Username	Problem	Language	Result	Execution time	Memory
232319		pedy4000	Raspad (COI17_raspad)	C++14	26 / 100	534 ms	632 KiB

raspad

#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;
}

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