oj.uz

답안 #876348

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
876348 2023-11-21T15:20:45 Z vjudge1 Tracks in the Snow (BOI13_tracks) C++17
0 / 100
 2000 ms 860244 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;

void solve()
{
	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;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
	return 0;
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2078 ms 524764 KB Time limit exceeded
2 Execution timed out 2081 ms 735428 KB Time limit exceeded
3 Execution timed out 2047 ms 743228 KB Time limit exceeded
4 Execution timed out 2045 ms 572360 KB Time limit exceeded
5 Execution timed out 2048 ms 667656 KB Time limit exceeded
6 Execution timed out 2060 ms 736708 KB Time limit exceeded
7 Execution timed out 2109 ms 784996 KB Time limit exceeded
8 Execution timed out 2058 ms 735616 KB Time limit exceeded
9 Execution timed out 2039 ms 4700 KB Time limit exceeded
10 Execution timed out 2049 ms 8796 KB Time limit exceeded
11 Execution timed out 2078 ms 444792 KB Time limit exceeded
12 Execution timed out 2085 ms 547492 KB Time limit exceeded
13 Execution timed out 2115 ms 592252 KB Time limit exceeded
14 Execution timed out 2102 ms 629852 KB Time limit exceeded
15 Execution timed out 2036 ms 5464 KB Time limit exceeded
16 Execution timed out 2081 ms 497212 KB Time limit exceeded
17 Execution timed out 2035 ms 21792 KB Time limit exceeded
18 Execution timed out 2081 ms 529828 KB Time limit exceeded

Subtask #2
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2037 ms 68184 KB Time limit exceeded
2 Execution timed out 2070 ms 194216 KB Time limit exceeded
3 Execution timed out 2138 ms 759268 KB Time limit exceeded
4 Execution timed out 2077 ms 771504 KB Time limit exceeded
5 Execution timed out 2088 ms 70920 KB Time limit exceeded
6 Execution timed out 2098 ms 368660 KB Time limit exceeded
7 Incorrect 807 ms 68404 KB Output isn't correct
8 Execution timed out 2009 ms 68184 KB Time limit exceeded
9 Execution timed out 2054 ms 301860 KB Time limit exceeded
10 Execution timed out 2039 ms 2392 KB Time limit exceeded
11 Execution timed out 2076 ms 68188 KB Time limit exceeded
12 Execution timed out 2060 ms 6748 KB Time limit exceeded
13 Execution timed out 2017 ms 194244 KB Time limit exceeded
14 Execution timed out 2052 ms 22024 KB Time limit exceeded
15 Execution timed out 2039 ms 325456 KB Time limit exceeded
16 Execution timed out 2037 ms 66864 KB Time limit exceeded
17 Execution timed out 2031 ms 45396 KB Time limit exceeded
18 Execution timed out 2032 ms 45524 KB Time limit exceeded
19 Execution timed out 2145 ms 824008 KB Time limit exceeded
20 Execution timed out 2029 ms 41180 KB Time limit exceeded
21 Execution timed out 2031 ms 73464 KB Time limit exceeded
22 Execution timed out 2009 ms 70740 KB Time limit exceeded
23 Execution timed out 2090 ms 123012 KB Time limit exceeded
24 Execution timed out 2094 ms 129304 KB Time limit exceeded
25 Execution timed out 2025 ms 224576 KB Time limit exceeded
26 Execution timed out 2136 ms 860244 KB Time limit exceeded
27 Execution timed out 2130 ms 859472 KB Time limit exceeded
28 Execution timed out 2028 ms 369520 KB Time limit exceeded
29 Execution timed out 2040 ms 559800 KB Time limit exceeded
30 Execution timed out 2028 ms 424396 KB Time limit exceeded
31 Execution timed out 2056 ms 685696 KB Time limit exceeded
32 Execution timed out 2127 ms 859960 KB Time limit exceeded