Submission #1265140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265140		kong_hby	Raspad (COI17_raspad)	C++20	100 / 100	595 ms	521720 KiB

raspad

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 10, M = 60;
int fx[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}, n, m, mi, mx, e[N][M][4], vis[N][M], c[N][M], ans;
void dfs(int x, int y){
	if(x < 0 || y < 0 || x > n || y > m || vis[x][y])return;
	vis[x][y] = 1;
	mi = min(mi, x), mx = max(mx, x);
	for(int i = 0; i < 4; i ++){
		if(!e[x][y][i]){
			dfs(x + fx[i][0], y + fx[i][1]);
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	// freopen("connect.in", "r", stdin);
	// freopen("connect.out", "w", stdout);
	cin >> n >> m;
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){
			char s;
			cin >> s;
			c[i][j] = s - '0';
		}
	}
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){
			if(c[i][j])ans += i * (n - i + 1);
			if(c[i][j] && c[i - 1][j])ans -= (i - 1) * (n - i + 1);
			if(c[i][j] && c[i][j - 1])ans -= i * (n - i + 1);
		}
	}
	for(int i = 0; i <= n; i ++){
		for(int j = 0; j <= m; j ++){
			e[i][j][0] = c[i + 1][j] && c[i + 1][j + 1];
			e[i][j][1] = c[i][j + 1] && c[i + 1][j + 1];
			e[i][j][2] = c[i][j] && c[i][j + 1];
			e[i][j][3] = c[i][j] && c[i + 1][j];
		}
	}
	dfs(0, 0);
	for(int i = 1; i < n; i ++){
		for(int j = 1; j < m; j ++){
			if(!vis[i][j]){
				mi = n, mx = 0;
				dfs(i, j);
				ans += mi * (n - mx);
			}
		}
	}
	cout << ans;
}

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