Submission #958064

#	Time	Username	Problem	Language	Result	Execution time	Memory
958064		lovrot	Raspad (COI17_raspad)	C++17	100 / 100	367 ms	24392 KiB

raspad

#include <cstdio> 
#include <queue> 
#include <vector> 
#include <algorithm> 

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef long long ll; 
typedef pair<int, int> pii; 

const int N = 1e5 + 10;
const int M = 60;
const int LX[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int LY[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

int n, m;
bool A[N][M]; 

ll F[N], _F[N]; 

void _add(ll *T, int x, ll val) {
	for(; x < N; x += x & -x) T[x] += val;
}

ll _sum(ll *T, int x) {
	ll ret = 0;
	for(; x; x -= x & -x) ret += T[x];
	return ret;
}

void add(int x, ll val) {
	_add(F, x, val); 
	_add(_F, x, val * (x - 1));
}

ll sum(int x) {
	return _sum(F, x) * x - _sum(_F, x);
}

bool BIO[N][M];
queue<pii> Q; 

pii bfs(int x, int y) {
	int mn = N, mx = 0;
	Q.push({x, y});
	BIO[x][y] = 1;
	for(; !Q.empty(); Q.pop()) {
		x = Q.front().X; 
		y = Q.front().Y;
		mn = min(mn, x); 
		mx = max(mx, x);
		for(int i = 0; i < 8; ++i) {
			int nx = x + LX[i], ny = y + LY[i]; 
			if(nx >= 0 && nx < N && ny >= 0 && ny < M && !A[nx][ny] && !BIO[nx][ny]) {
				BIO[nx][ny] = 1;
				Q.push({nx, ny});
			}
		}
	}
	return {mx, mn};
}

vector<int> U[N];

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j) {
			char c; scanf(" %c", &c); 
			A[i][j] = c == '1'; 
		}

	for(int i = 1; i <= n; ++i) 
		for(int j = 1; j <= m; ++j) 
			if(!A[i][j] && !BIO[i][j]) {
				pii res = bfs(i, j);
				U[res.Y - 1].PB(res.X + 1);	
//				printf("%d @ %d\n", res.Y, res.X);
			}
	
	ll ans = 0;
	for(int i = n; i >= 1; --i) {
		for(int r : U[i]) add(r, 1);
		int e = 0, _e = 0, v = 0, f = 0;
		for(int j = 1; j <= m; ++j) {
			v += A[i][j];
			e += A[i][j] & A[i][j - 1];
			_e += A[i][j] & A[i + 1][j];
			f += A[i][j] & A[i][j - 1] & A[i + 1][j] & A[i + 1][j - 1];
		}
//		printf("f %d v %d e %d +e %d\n", f, v, e, _e);
		add(i, -e); add(i, v); 
		add(i + 1, -_e); add(i + 1, f); 
		ans += sum(n); 
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

raspad.cpp: In function 'int main()':
raspad.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
raspad.cpp:73:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |    char c; scanf(" %c", &c);
      |            ~~~~~^~~~~~~~~~~

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