oj.uz

Submission #486977

# Submission time Handle Problem Language Result Execution time Memory
486977 2021-11-13T16:51:08 Z rainboy Raspad (COI17_raspad) C
100 / 100
 388 ms 108228 KB 
#include <stdio.h>
#include <string.h>

#define N	100000
#define M	50

int di[] = { -1, 0, 1, 0 };
int dj[] = { 0, -1, 0, 1 };

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int cross(int x1, int y1, int x2, int y2) {
	return x1 * y2 - x2 * y1;
}

int main() {
	static char cc[N][M + 1], visited[N * M * 4];
	static int nxt[N * M * 4];
	int n, m, h, h_, i, i_, j, j_, ijh;
	long long ans;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	ans = 0;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			if (cc[i][j] == '1') {
				ans += (long long) (i + 1) * (n - i);
				if (j > 0 && cc[i][j - 1] == '1')
					ans -= (long long) (i + 1) * (n - i);
				if (i > 0 && cc[i - 1][j] == '1')
					ans -= (long long) i * (n - i);
			}
	memset(nxt, -1, n * m * 4 * sizeof *nxt);
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			if (cc[i][j] == '1')
				for (h = 0; h < 4; h++) {
					i_ = i - di[h], j_ = j - dj[h];
					if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m && cc[i_][j_] == '1')
						for (h_ = (h + 3) % 4; ; h_ = (h_ + 1) % 4) {
							i_ = i + di[h_], j_ = j + dj[h_];
							if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m && cc[i_][j_] == '1') {
								nxt[(i * m + j) * 4 + h] = (i_ * m + j_) * 4 + h_;
								break;
							}
						}
				}
	for (ijh = 0; ijh < n * m * 4; ijh++)
		if (nxt[ijh] != -1 && !visited[ijh]) {
			int imn, imx, a;

			imn = n, imx = -1, a = 0;
			while (!visited[ijh]) {
				visited[ijh] = 1;
				i = ijh / 4 / m, j = ijh / 4 % m, h = ijh % 4;
				a += cross(i - di[h], j - dj[h], i, j);
				imn = min(imn, i), imx = max(imx, i);
				ijh = nxt[ijh];
			}
			if (a < 0)
				ans += (long long) (imn + 1) * (n - imx);
		}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

raspad.c: In function 'main':
raspad.c:23:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
raspad.c:25:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 392 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 412 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 392 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 412 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 1228 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 4 ms 1356 KB Output is correct
10 Correct 2 ms 1144 KB Output is correct
11 Correct 3 ms 1356 KB Output is correct
12 Correct 2 ms 972 KB Output is correct
13 Correct 2 ms 1228 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 17172 KB Output is correct
2 Correct 69 ms 36188 KB Output is correct
3 Correct 104 ms 36160 KB Output is correct
4 Correct 32 ms 27212 KB Output is correct
5 Correct 23 ms 10980 KB Output is correct
6 Correct 77 ms 36140 KB Output is correct
7 Correct 58 ms 36084 KB Output is correct
8 Correct 57 ms 29020 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 392 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 412 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 1228 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 4 ms 1356 KB Output is correct
10 Correct 2 ms 1144 KB Output is correct
11 Correct 3 ms 1356 KB Output is correct
12 Correct 2 ms 972 KB Output is correct
13 Correct 2 ms 1228 KB Output is correct
14 Correct 54 ms 17172 KB Output is correct
15 Correct 69 ms 36188 KB Output is correct
16 Correct 104 ms 36160 KB Output is correct
17 Correct 32 ms 27212 KB Output is correct
18 Correct 23 ms 10980 KB Output is correct
19 Correct 77 ms 36140 KB Output is correct
20 Correct 58 ms 36084 KB Output is correct
21 Correct 57 ms 29020 KB Output is correct
22 Correct 185 ms 70028 KB Output is correct
23 Correct 366 ms 108056 KB Output is correct
24 Correct 388 ms 108036 KB Output is correct
25 Correct 219 ms 108100 KB Output is correct
26 Correct 258 ms 107972 KB Output is correct
27 Correct 201 ms 87484 KB Output is correct
28 Correct 273 ms 87468 KB Output is correct
29 Correct 295 ms 108084 KB Output is correct
30 Correct 236 ms 107980 KB Output is correct
31 Correct 233 ms 108228 KB Output is correct
32 Correct 155 ms 107972 KB Output is correct
33 Correct 219 ms 95468 KB Output is correct
34 Correct 256 ms 97408 KB Output is correct