Submission #1091666

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1091666	2024-09-21T18:22:36 Z	ef10	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	616 ms	90728 KB

tracks

// Source: https://usaco.guide/general/io

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

int H, W;
string M[4005];
bool v[4005][4005];

int main() {
	cin >> H >> W;
	for (int i = 0; i < H; i++) {
		cin >> M[i];
	}
	if (M[0][0] == '.') return 0;
	deque<pair<int,int> > q;
	q.push_back(make_pair(0,0));
	v[0][0] = true;
	int res = 1;
	char current = M[0][0];
	while (!q.empty()) {
		auto c = q.front();
		q.pop_front();
		if (M[c.first][c.second] != current) {
			res++;
			current = M[c.first][c.second];
		}
		for (auto i : {-1,1}) {
			for (auto j : {0,1}) {
				if (j==0) {
					if (((i < 0 && c.first > 0) || (i > 0 && c.first < H-1)) && !v[c.first+i][c.second] && M[c.first+i][c.second] != '.') {
						v[c.first+i][c.second] = true;
						if (M[c.first][c.second] == M[c.first+i][c.second]) {
							q.push_front(make_pair(c.first+i,c.second));
						} else {
							q.push_back(make_pair(c.first+i,c.second));
						}
					}
				} else {
					if (((i < 0 && c.second > 0) || (i > 0 && c.second < W-1)) && !v[c.first][c.second+i] && M[c.first][c.second+i] != '.') {
						v[c.first][c.second+i] = true;
						if (M[c.first][c.second] == M[c.first][c.second+i]) {
							q.push_front(make_pair(c.first,c.second+i));
						} else {
							q.push_back(make_pair(c.first,c.second+i));
						}
					}
				}
			}
		}
	}
	cout << res << endl;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	3164 KB	Output is correct
2	Correct	0 ms	604 KB	Output is correct
3	Correct	0 ms	604 KB	Output is correct
4	Correct	6 ms	2884 KB	Output is correct
5	Correct	3 ms	1884 KB	Output is correct
6	Correct	0 ms	604 KB	Output is correct
7	Correct	1 ms	604 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	1 ms	984 KB	Output is correct
10	Correct	3 ms	1628 KB	Output is correct
11	Correct	3 ms	1352 KB	Output is correct
12	Correct	5 ms	1884 KB	Output is correct
13	Correct	3 ms	1704 KB	Output is correct
14	Correct	3 ms	1884 KB	Output is correct
15	Correct	9 ms	3140 KB	Output is correct
16	Correct	12 ms	3164 KB	Output is correct
17	Correct	9 ms	3028 KB	Output is correct
18	Correct	7 ms	2888 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	15452 KB	Output is correct
2	Correct	47 ms	9336 KB	Output is correct
3	Correct	304 ms	61768 KB	Output is correct
4	Correct	74 ms	18516 KB	Output is correct
5	Correct	189 ms	32428 KB	Output is correct
6	Correct	608 ms	75724 KB	Output is correct
7	Correct	7 ms	16220 KB	Output is correct
8	Correct	7 ms	15452 KB	Output is correct
9	Correct	2 ms	832 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	7 ms	15964 KB	Output is correct
12	Correct	1 ms	1116 KB	Output is correct
13	Correct	41 ms	9300 KB	Output is correct
14	Correct	26 ms	6748 KB	Output is correct
15	Correct	28 ms	7248 KB	Output is correct
16	Correct	19 ms	3420 KB	Output is correct
17	Correct	109 ms	19964 KB	Output is correct
18	Correct	81 ms	19796 KB	Output is correct
19	Correct	103 ms	18520 KB	Output is correct
20	Correct	78 ms	17408 KB	Output is correct
21	Correct	181 ms	33360 KB	Output is correct
22	Correct	199 ms	32428 KB	Output is correct
23	Correct	214 ms	27500 KB	Output is correct
24	Correct	181 ms	33364 KB	Output is correct
25	Correct	367 ms	61776 KB	Output is correct
26	Correct	418 ms	89632 KB	Output is correct
27	Correct	541 ms	90728 KB	Output is correct
28	Correct	584 ms	75580 KB	Output is correct
29	Correct	616 ms	76552 KB	Output is correct
30	Correct	554 ms	81136 KB	Output is correct
31	Correct	418 ms	35412 KB	Output is correct
32	Correct	498 ms	79824 KB	Output is correct