Submission #36527

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
36527	2017-12-10T08:04:17 Z	cheater2k	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1303 ms	448676 KB

tracks

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

const int N = 4005;
const int dx[] = {0, 0, -1, +1};
const int dy[] = {-1, +1, 0, 0};

int r, c;
string a[N];
bool vis[N][N];
int ans;

void bfs(queue< pair<int,int> > &q1, queue< pair<int,int> > &q2) {
	if (q1.empty()) return;
	++ans;
	while(!q1.empty()) {
		int x = q1.front().first, y = q1.front().second; q1.pop();
		for (int dir = 0; dir < 4; ++dir) {
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			if (nx < 0 || nx >= r || ny < 0 || ny >= c || a[nx][ny] == '.' || vis[nx][ny]) continue;
			vis[nx][ny] = true;
			if (a[nx][ny] != a[x][y]) q2.push(make_pair(nx, ny));
			else q1.push(make_pair(nx, ny));
		}
	}
	bfs(q2, q1);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> r >> c;
	for (int i = 0; i < r; ++i) {
		cin >> a[i]; // 0-based index
	}
	queue < pair<int,int> > q1, q2;
	q1.push(make_pair(0,0));
	vis[0][0] = true;
	bfs(q1, q2);

	printf("%d\n", ans);
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	18232 KB	Output is correct
2	Correct	0 ms	17968 KB	Output is correct
3	Correct	0 ms	17968 KB	Output is correct
4	Correct	6 ms	18232 KB	Output is correct
5	Correct	0 ms	17968 KB	Output is correct
6	Correct	0 ms	17968 KB	Output is correct
7	Correct	0 ms	17968 KB	Output is correct
8	Correct	0 ms	17968 KB	Output is correct
9	Correct	0 ms	17968 KB	Output is correct
10	Correct	3 ms	17968 KB	Output is correct
11	Correct	3 ms	17968 KB	Output is correct
12	Correct	3 ms	18100 KB	Output is correct
13	Correct	0 ms	17968 KB	Output is correct
14	Correct	0 ms	17968 KB	Output is correct
15	Correct	9 ms	18232 KB	Output is correct
16	Correct	9 ms	18232 KB	Output is correct
17	Correct	6 ms	18232 KB	Output is correct
18	Correct	6 ms	18232 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	18320 KB	Output is correct
2	Correct	46 ms	19552 KB	Output is correct
3	Correct	219 ms	90740 KB	Output is correct
4	Correct	69 ms	21928 KB	Output is correct
5	Correct	223 ms	448676 KB	Output is correct
6	Correct	1233 ms	45796 KB	Output is correct
7	Correct	0 ms	18256 KB	Output is correct
8	Correct	3 ms	18320 KB	Output is correct
9	Correct	0 ms	17968 KB	Output is correct
10	Correct	0 ms	18080 KB	Output is correct
11	Correct	0 ms	18044 KB	Output is correct
12	Correct	0 ms	18872 KB	Output is correct
13	Correct	53 ms	19552 KB	Output is correct
14	Correct	26 ms	18892 KB	Output is correct
15	Correct	23 ms	32116 KB	Output is correct
16	Correct	26 ms	18628 KB	Output is correct
17	Correct	139 ms	22392 KB	Output is correct
18	Correct	113 ms	73708 KB	Output is correct
19	Correct	59 ms	21928 KB	Output is correct
20	Correct	53 ms	32692 KB	Output is correct
21	Correct	143 ms	58728 KB	Output is correct
22	Correct	236 ms	448672 KB	Output is correct
23	Correct	326 ms	26676 KB	Output is correct
24	Correct	163 ms	167796 KB	Output is correct
25	Correct	503 ms	248968 KB	Output is correct
26	Correct	716 ms	31316 KB	Output is correct
27	Correct	993 ms	37312 KB	Output is correct
28	Correct	1246 ms	45796 KB	Output is correct
29	Correct	1303 ms	44268 KB	Output is correct
30	Correct	1016 ms	43208 KB	Output is correct
31	Correct	993 ms	29472 KB	Output is correct
32	Correct	973 ms	36340 KB	Output is correct