Submission #1001232

# Submission time Handle Problem Language Result Execution time Memory
1001232 2024-06-18T17:17:39 Z vjudge3 Tracks in the Snow (BOI13_tracks) C++17
89.0625 / 100
1283 ms 1048576 KB
#include <bits/stdc++.h>
using namespace std;

char g[4005][4005];
bitset<4005> vis[4005];
vector<pair<short, short>> layer[1000005];
int h, w, dep = 1;
const int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};

void dfs (int r, int c, char ch) {
	if (!vis[r][c]) layer[dep].push_back({r, c});
	vis[r][c] = true;
	for (int k = 0; k < 4; k++) {
		int rv = r + dr[k], cv = c + dc[k];
		if (rv >= 1 && rv <= h && cv >= 1 && cv <= w && !vis[rv][cv] && g[rv][cv] == ch) dfs(rv, cv, ch);
	}
}

int main () {
	cin >> h >> w;
	for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) cin >> g[i][j];
	dfs(1, 1, g[1][1]);
	while (true) {
		dep++;
		for (auto& [r, c] : layer[dep-1]) dfs(r, c, "RF"[(dep & 1) ^ (g[1][1] == 'R')]);
		layer[dep-1].clear();
		if (layer[dep].empty()) {
			cout << dep-1 << '\n';
			return 0;
		}
	}
	return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 22 ms 30300 KB Output is correct
2 Correct 4 ms 27228 KB Output is correct
3 Correct 5 ms 27312 KB Output is correct
4 Correct 15 ms 31580 KB Output is correct
5 Correct 6 ms 27228 KB Output is correct
6 Correct 3 ms 27260 KB Output is correct
7 Correct 4 ms 27228 KB Output is correct
8 Correct 4 ms 27228 KB Output is correct
9 Correct 4 ms 27228 KB Output is correct
10 Correct 7 ms 27484 KB Output is correct
11 Correct 7 ms 28324 KB Output is correct
12 Correct 11 ms 27740 KB Output is correct
13 Correct 8 ms 27224 KB Output is correct
14 Correct 7 ms 27300 KB Output is correct
15 Correct 18 ms 30108 KB Output is correct
16 Correct 20 ms 30400 KB Output is correct
17 Correct 16 ms 29788 KB Output is correct
18 Correct 15 ms 31580 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 8 ms 41308 KB Output is correct
2 Correct 72 ms 34968 KB Output is correct
3 Correct 601 ms 73556 KB Output is correct
4 Correct 131 ms 36764 KB Output is correct
5 Runtime error 327 ms 144528 KB Execution killed with signal 11
6 Correct 992 ms 217868 KB Output is correct
7 Correct 8 ms 42072 KB Output is correct
8 Correct 8 ms 41308 KB Output is correct
9 Correct 7 ms 27736 KB Output is correct
10 Correct 5 ms 27740 KB Output is correct
11 Correct 7 ms 41564 KB Output is correct
12 Correct 5 ms 27484 KB Output is correct
13 Correct 71 ms 34964 KB Output is correct
14 Correct 40 ms 33360 KB Output is correct
15 Correct 46 ms 36180 KB Output is correct
16 Correct 36 ms 31376 KB Output is correct
17 Correct 169 ms 43920 KB Output is correct
18 Correct 150 ms 53640 KB Output is correct
19 Correct 121 ms 36752 KB Output is correct
20 Correct 131 ms 40528 KB Output is correct
21 Correct 350 ms 58260 KB Output is correct
22 Runtime error 325 ms 144520 KB Execution killed with signal 11
23 Correct 339 ms 54356 KB Output is correct
24 Runtime error 357 ms 146768 KB Execution killed with signal 11
25 Runtime error 567 ms 151636 KB Execution killed with signal 11
26 Runtime error 788 ms 1048576 KB Execution killed with signal 9
27 Correct 1283 ms 840128 KB Output is correct
28 Correct 972 ms 219200 KB Output is correct
29 Correct 950 ms 189684 KB Output is correct
30 Correct 1109 ms 360780 KB Output is correct
31 Correct 664 ms 80932 KB Output is correct
32 Correct 1174 ms 611744 KB Output is correct