oj.uz

답안 #876353

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
876353 2023-11-21T15:28:02 Z vjudge1 Tracks in the Snow (BOI13_tracks) C++17
16.4583 / 100
 2000 ms 812824 KB 
#include <bits/stdc++.h>
using namespace std;

const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
const int MAXN = 4000 + 5;
char ch;
int n, m, ans;
int g[MAXN][MAXN];
bool seen[MAXN][MAXN];
queue<pair<int, int>> qq;

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		ch = getchar();
		for (int j = 1; j <= m; j++)
		{
			ch = getchar();
			switch (ch)
			{
			case 'R':
				g[i][j] = 0;
				break;
			case '.':
				g[i][j] = -1;
				break;
			case 'F':
				g[i][j] = 1;
				break;
			}
		}
	}
	while (true)
	{
		for (int i = 0; i <= n + 1; i++)
			for (int j = 0; j <= m + 1; j++)
				seen[i][j] = false;
		ans++;
		qq.push(make_pair(1, 1));
		while (!qq.empty())
		{
			pair<int, int> now = qq.front();
			qq.pop();
			int x = now.first, y = now.second;
			seen[x][y] = true;
			for (int i = 0; i < 4; i++)
			{
				int fx = x + dx[i], fy = y + dy[i];
				if (fx < 1 || fy < 1 || fx > n || fy > m || g[x][y] != g[fx][fy] || seen[fx][fy])
					continue;
				qq.push(make_pair(fx, fy));
			}
		}
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				if (seen[i][j])
					g[i][j] = 1 - g[i][j];
		bool ra = false, fo = false;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
			{
				if (g[i][j] == 0)
					ra = true;
				else if (g[i][j] == 1)
					fo = true;
			}
		if (!(ra && fo))
			break;
	}
	cout << ans + 1 << endl;
	return 0;
}

Subtask #1
3.33333333333 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2110 ms 484072 KB Time limit exceeded
2 Correct 1 ms 2392 KB Output is correct
3 Execution timed out 2109 ms 718612 KB Time limit exceeded
4 Execution timed out 2088 ms 596192 KB Time limit exceeded
5 Execution timed out 2085 ms 427532 KB Time limit exceeded
6 Correct 2 ms 2392 KB Output is correct
7 Execution timed out 2124 ms 740872 KB Time limit exceeded
8 Execution timed out 2036 ms 427784 KB Time limit exceeded
9 Execution timed out 2040 ms 72696 KB Time limit exceeded
10 Execution timed out 2033 ms 511504 KB Time limit exceeded
11 Execution timed out 2107 ms 774964 KB Time limit exceeded
12 Execution timed out 2053 ms 313236 KB Time limit exceeded
13 Execution timed out 2063 ms 417300 KB Time limit exceeded
14 Execution timed out 2059 ms 425520 KB Time limit exceeded
15 Execution timed out 2061 ms 275108 KB Time limit exceeded
16 Execution timed out 2097 ms 482216 KB Time limit exceeded
17 Execution timed out 2040 ms 486772 KB Time limit exceeded
18 Execution timed out 2090 ms 596488 KB Time limit exceeded

Subtask #2
13.125 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1852 ms 76568 KB Output is correct
2 Execution timed out 2045 ms 237644 KB Time limit exceeded
3 Execution timed out 2062 ms 93200 KB Time limit exceeded
4 Execution timed out 2064 ms 117368 KB Time limit exceeded
5 Execution timed out 2021 ms 61896 KB Time limit exceeded
6 Execution timed out 2040 ms 211504 KB Time limit exceeded
7 Correct 1393 ms 78676 KB Output is correct
8 Correct 1920 ms 76628 KB Output is correct
9 Execution timed out 2057 ms 20128 KB Time limit exceeded
10 Correct 325 ms 2516 KB Output is correct
11 Correct 738 ms 78572 KB Output is correct
12 Correct 1434 ms 6748 KB Output is correct
13 Execution timed out 2075 ms 235756 KB Time limit exceeded
14 Execution timed out 2064 ms 173580 KB Time limit exceeded
15 Execution timed out 2036 ms 23128 KB Time limit exceeded
16 Execution timed out 2059 ms 118112 KB Time limit exceeded
17 Execution timed out 2079 ms 274072 KB Time limit exceeded
18 Execution timed out 2004 ms 41416 KB Time limit exceeded
19 Execution timed out 2050 ms 118284 KB Time limit exceeded
20 Execution timed out 2009 ms 37656 KB Time limit exceeded
21 Execution timed out 2017 ms 64084 KB Time limit exceeded
22 Execution timed out 2093 ms 61904 KB Time limit exceeded
23 Execution timed out 2061 ms 134168 KB Time limit exceeded
24 Execution timed out 2041 ms 64080 KB Time limit exceeded
25 Execution timed out 2040 ms 78600 KB Time limit exceeded
26 Execution timed out 2061 ms 812824 KB Time limit exceeded
27 Execution timed out 2040 ms 742276 KB Time limit exceeded
28 Execution timed out 2066 ms 211444 KB Time limit exceeded
29 Execution timed out 2081 ms 757936 KB Time limit exceeded
30 Execution timed out 2036 ms 473588 KB Time limit exceeded
31 Execution timed out 2063 ms 397296 KB Time limit exceeded
32 Execution timed out 2056 ms 102880 KB Time limit exceeded