Submission #563318

#	Time	Username	Problem	Language	Result	Execution time	Memory
563318		keta_tsimakuridze	Raspad (COI17_raspad)	C++11	100 / 100	704 ms	117524 KiB

raspad

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"
#define mp make_pair
const int N = 1e5 + 5, M = 54, mod = 1e9 + 7; //!
int t, ok[N][M],up[N][M], down[N][M]; 
pii p[N][M];
char c[N][M];
pii find(int x,int y) {
	return (p[x][y] == mp(x, y) ? p[x][y] : p[x][y] = find(p[x][y].f, p[x][y].s));
}
void merge(int x, int y, int i, int j) {
	pii p1 = find(x, y), p2 = find(i, j);
	p[p2.f][p2.s] = p1;
	ok[p1.f][p1.s] &= ok[p2.f][p2.s];
	up[p1.f][p1.s] = min(up[p1.f][p1.s], up[p2.f][p2.s]);
	down[p1.f][p1.s] = max(down[p1.f][p1.s], down[p2.f][p2.s]);
}
main() {
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int n, m;
	long long ans = 0;
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			cin >> c[i][j];
			if(c[i][j] == '1') ans += (long long)i * (n - i + 1);
		}
	}
	
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			if(c[i][j] == '1') {
				if(c[i + 1][j] == '1') {
					ans -= (long long)i * (n - i);
				}
				if(c[i][j + 1] == '1') {
					ans -= (long long)i * (n - i + 1);
				}
			}
		}
	}
	for(int i = 0; i <= n + 1; i++) {
		for(int j = 0; j <= m + 1; j++) {
			p[i][j] = {i, j}, up[i][j] = down[i][j] = i;
			ok[i][j] = (i && j && (i < n + 1) && (j < m + 1));
		}
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			if(c[i][j] != '1' || c[i + 1][j] != '1') merge(i + 1, j, i + 1, j + 1); 
			if(c[i][j] != '1' || c[i][j + 1] != '1') merge(i, j + 1, i + 1, j + 1);
			if(c[i][j] != '1' || c[i - 1][j] != '1') merge(i, j, i, j + 1);
			if(c[i][j] != '1' || c[i][j - 1] != '1') merge(i, j, i + 1, j);
		}
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			if(find(i, j) == make_pair(i, j)) {
				if(ok[i][j]) {
					ans += (long long)(up[i][j] - 1) * (n - down[i][j] + 1); 
				}
			}
		}
	}
	cout << ans;
}

Compilation message (stderr)

raspad.cpp:22:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   22 | main() {
      | ^~~~

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