Submission #1037013

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1037013	2024-07-27T21:50:07 Z	sssamui	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	538 ms	28804 KB

tracks

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;

vector<int> radd = { -1, 0, 1, 0 };
vector<int> cadd = { 0, -1, 0, 1 };

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int h, w;
	cin >> h >> w;
	vector<vector<char>> trk(h + 2, vector<char>(w + 2, '.'));
	for (int i = 1; i <= h; i++) for (int j = 1; j <= w; j++) cin >> trk[i][j];

	int ans = 0;
	vector<vector<bool>> vis(h + 2, vector<bool>(w + 2, false));
	queue<pair<int, int>> bfs;
	queue<pair<int, int>> nxt;
	bfs.push({ 1, 1 });
	vis[1][1] = true;
	while (!bfs.empty())
	{
		ans++;
		while (!bfs.empty())
		{
			int r = bfs.front().first, c = bfs.front().second;
			bfs.pop();
			for (int dir = 0; dir < 4; dir++) if (!vis[r + radd[dir]][c + cadd[dir]])
			{
				vis[r + radd[dir]][c + cadd[dir]] = true;
				if (trk[r + radd[dir]][c + cadd[dir]] == trk[r][c]) bfs.push({ r + radd[dir], c + cadd[dir] });
				else if (trk[r + radd[dir]][c + cadd[dir]] != '.') nxt.push({ r + radd[dir], c + cadd[dir] });
			}
		}

		while (!nxt.empty())
		{
			bfs.push(nxt.front());
			nxt.pop();
		}
	}

	cout << ans;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	600 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	5 ms	824 KB	Output is correct
5	Correct	2 ms	348 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	2 ms	348 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Correct	4 ms	604 KB	Output is correct
13	Correct	2 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	7 ms	720 KB	Output is correct
16	Correct	8 ms	604 KB	Output is correct
17	Correct	6 ms	604 KB	Output is correct
18	Correct	5 ms	604 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	856 KB	Output is correct
2	Correct	33 ms	2292 KB	Output is correct
3	Correct	218 ms	18356 KB	Output is correct
4	Correct	51 ms	4732 KB	Output is correct
5	Correct	150 ms	10580 KB	Output is correct
6	Correct	538 ms	28804 KB	Output is correct
7	Correct	1 ms	856 KB	Output is correct
8	Correct	2 ms	860 KB	Output is correct
9	Correct	2 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	860 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	35 ms	2316 KB	Output is correct
14	Correct	20 ms	1372 KB	Output is correct
15	Correct	13 ms	1628 KB	Output is correct
16	Correct	16 ms	1224 KB	Output is correct
17	Correct	92 ms	4944 KB	Output is correct
18	Correct	53 ms	4948 KB	Output is correct
19	Correct	50 ms	4700 KB	Output is correct
20	Correct	49 ms	4180 KB	Output is correct
21	Correct	121 ms	10980 KB	Output is correct
22	Correct	137 ms	10576 KB	Output is correct
23	Correct	185 ms	9176 KB	Output is correct
24	Correct	124 ms	10576 KB	Output is correct
25	Correct	282 ms	18256 KB	Output is correct
26	Correct	238 ms	14164 KB	Output is correct
27	Correct	360 ms	20052 KB	Output is correct
28	Correct	504 ms	28612 KB	Output is correct
29	Correct	537 ms	27016 KB	Output is correct
30	Correct	452 ms	25912 KB	Output is correct
31	Correct	459 ms	12380 KB	Output is correct
32	Correct	298 ms	19088 KB	Output is correct