oj.uz

Submission #958051

# Submission time Handle Problem Language Result Execution time Memory
958051 2024-04-04T18:22:10 Z lovrot Raspad (COI17_raspad) C++17
35 / 100
 233 ms 20200 KB 
#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 LOG = 17;
const int N = 1 << LOG;
const int M = 51;
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("%d %lld\n", i, sum(n));
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 12116 KB Output is correct
2 Incorrect 138 ms 12020 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 12116 KB Output is correct
2 Incorrect 138 ms 12020 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 12380 KB Output is correct
2 Correct 231 ms 19080 KB Output is correct
3 Correct 210 ms 19952 KB Output is correct
4 Correct 183 ms 18768 KB Output is correct
5 Correct 162 ms 12884 KB Output is correct
6 Correct 233 ms 19104 KB Output is correct
7 Correct 197 ms 20200 KB Output is correct
8 Correct 195 ms 18824 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 12116 KB Output is correct
2 Incorrect 138 ms 12020 KB Output isn't correct
3 Halted 0 ms 0 KB -