답안 #1001240

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1001240	2024-06-18T17:23:35 Z	vjudge3	Tracks in the Snow (BOI13_tracks)	C++17	97.8125 / 100	1328 ms	1048576 KB

tracks

#include <bits/stdc++.h>
using namespace std;

bitset<4005> vis[4005], occ[4005], fox[4005];
vector<pair<short, short>> cur;
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, bool f) {
	if (!vis[r][c]) cur.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] && occ[rv][cv] && fox[rv][cv] == f) dfs(rv, cv, f);
	}
}

int main () {
	cin >> h >> w;
	for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) {
		char ch;
		cin >> ch;
		if (ch != '.') occ[i][j] = true;
		if (ch == 'F') fox[i][j] = true;
	}
	dfs(1, 1, fox[1][1]);
	while (true) {
		vector<pair<short, short>> last;
		last.swap(cur);
		for (auto& [r, c] : last) dfs(r, c, (dep & 1) ^ fox[1][1]);
		last.clear();
		if (cur.empty()) {
			cout << dep << '\n';
			return 0;
		}
		dep++;
	}
	return 0;
}

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	17 ms	3416 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	12 ms	5212 KB	Output is correct
5	Correct	5 ms	2860 KB	Output is correct
6	Correct	0 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	4 ms	2652 KB	Output is correct
11	Correct	3 ms	3676 KB	Output is correct
12	Correct	7 ms	2908 KB	Output is correct
13	Correct	4 ms	2808 KB	Output is correct
14	Correct	4 ms	2908 KB	Output is correct
15	Correct	16 ms	3364 KB	Output is correct
16	Correct	18 ms	3644 KB	Output is correct
17	Correct	14 ms	3080 KB	Output is correct
18	Correct	11 ms	5208 KB	Output is correct

Subtask #2

67.8125 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	6492 KB	Output is correct
2	Correct	77 ms	6168 KB	Output is correct
3	Correct	614 ms	15356 KB	Output is correct
4	Correct	149 ms	7592 KB	Output is correct
5	Correct	431 ms	11020 KB	Output is correct
6	Correct	1096 ms	179540 KB	Output is correct
7	Correct	4 ms	6744 KB	Output is correct
8	Correct	5 ms	6492 KB	Output is correct
9	Correct	4 ms	3172 KB	Output is correct
10	Correct	2 ms	2908 KB	Output is correct
11	Correct	4 ms	6748 KB	Output is correct
12	Correct	3 ms	2652 KB	Output is correct
13	Correct	75 ms	6236 KB	Output is correct
14	Correct	44 ms	5716 KB	Output is correct
15	Correct	50 ms	5724 KB	Output is correct
16	Correct	33 ms	3408 KB	Output is correct
17	Correct	181 ms	8016 KB	Output is correct
18	Correct	174 ms	7908 KB	Output is correct
19	Correct	149 ms	7616 KB	Output is correct
20	Correct	144 ms	7412 KB	Output is correct
21	Correct	339 ms	11344 KB	Output is correct
22	Correct	399 ms	10832 KB	Output is correct
23	Correct	363 ms	10320 KB	Output is correct
24	Correct	394 ms	11088 KB	Output is correct
25	Correct	659 ms	15184 KB	Output is correct
26	Runtime error	882 ms	1048576 KB	Execution killed with signal 9
27	Correct	1328 ms	814324 KB	Output is correct
28	Correct	1064 ms	181752 KB	Output is correct
29	Correct	1052 ms	150512 KB	Output is correct
30	Correct	1120 ms	333540 KB	Output is correct
31	Correct	751 ms	13264 KB	Output is correct
32	Correct	1297 ms	587168 KB	Output is correct