oj.uz

Submission #1030952

# Submission time Handle Problem Language Result Execution time Memory
1030952 2024-07-22T12:50:47 Z fv3 Rectangles (IOI19_rect) C++14
13 / 100
 457 ms 545228 KB 
#include "rect.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int N, M;
int l, r, t, d, cnt;

vector<vector<int>> grid, visited;
void DFS(int x, int y)
{
	visited[y][x] = 1; cnt++;
	l = min(l, x); r = max(r, x);
	t = min(t, y); d = max(d, y);

	if (x && !grid[y][x-1] && !visited[y][x-1])
		DFS(x-1, y);
	if (y && !grid[y-1][x] && !visited[y-1][x])
		DFS(x, y-1);
	if (x+1<M && !grid[y][x+1] && !visited[y][x+1])
		DFS(x+1, y);
	if (y+1<N && !grid[y+1][x] && !visited[y+1][x])
		DFS(x, y+1);
}

ll count_rectangles(vector<vector<int>> a) 
{
	N = a.size();
	M = a[0].size();

	grid = a;
	visited = vector<vector<int>>(N, vector<int>(M));

	ll res = 0;
	for (int y = 1; y < N-1; y++)
	{
		for (int x = 1; x < M-1; x++)
		{
			if (visited[y][x] || grid[y][x]) continue;
			l = r = x;
			t = d = y;
			cnt = 0;
			DFS(x, y);

			if (cnt == (r - l + 1) * (d - t + 1) && l && t && d < N-1 && r < M-1)
				res++;
		}
	}

	return res;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 86 ms 45432 KB Output is correct
3 Correct 193 ms 107436 KB Output is correct
4 Correct 200 ms 108088 KB Output is correct
5 Correct 196 ms 108116 KB Output is correct
6 Correct 209 ms 194536 KB Output is correct
7 Correct 414 ms 460624 KB Output is correct
8 Correct 457 ms 545228 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -