Submission #26358

#	Time	Username	Problem	Language	Result	Execution time	Memory
26358		kdh9949	Raspad (COI17_raspad)	C++14	100 / 100	743 ms	353704 KiB

raspad

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
int n, m, mx, Mx, e[100010][55][4], vis[100010][55], ts;
char b[100010][55];
ll ans;

void ff(int x, int y){
	if(x < 0 || y < 0 || x > n || y > m || vis[x][y]) return;
	vis[x][y] = 1;
	mx = min(mx, x); Mx = max(Mx, x);
	for(int i = 0; i < 4; i++) if(!e[x][y][i]) ff(x + dx[i], y + dy[i]);
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%s", b[i] + 1);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			b[i][j] -= '0';
			if(b[i][j]) ans += 1LL * i * (n + 1 - i);
			if(b[i][j] && b[i - 1][j]) ans -= 1LL * (i - 1) * (n + 1 - i);
			if(b[i][j] && b[i][j - 1]) ans -= 1LL * i * (n + 1 - i);
		}
	}
	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= m; j++){
			e[i][j][0] = b[i + 1][j] && b[i + 1][j + 1];
			e[i][j][1] = b[i][j + 1] && b[i + 1][j + 1];
			e[i][j][2] = b[i][j] && b[i][j + 1];
			e[i][j][3] = b[i][j] && b[i + 1][j];
		}
	}
	ff(0, 0);
	for(int i = 1; i < n; i++){
		for(int j = 1; j < m; j++){
			if(!vis[i][j]){
				mx = n; Mx = 0;
				ff(i, j);
				ans += 1LL * mx * (n - Mx);
			}
		}
	}
	printf("%lld\n", ans);
}

Compilation message (stderr)

raspad.cpp: In function 'int main()':
raspad.cpp:18:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
raspad.cpp:19:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= n; i++) scanf("%s", b[i] + 1);
                                                   ^

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