Submission #1036996

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1036996	2024-07-27T21:13:07 Z	sssamui	Tracks in the Snow (BOI13_tracks)	C++17	2.1875 / 100	139 ms	34056 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 = { -1, 0, 1, 0 };

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));
	if (trk[1][1] != '.')
	{
		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

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	856 KB	Output isn't correct
2	Incorrect	0 ms	348 KB	Output isn't correct
3	Incorrect	0 ms	348 KB	Output isn't correct
4	Incorrect	2 ms	604 KB	Output isn't correct
5	Incorrect	1 ms	604 KB	Output isn't correct
6	Incorrect	0 ms	348 KB	Output isn't correct
7	Incorrect	0 ms	348 KB	Output isn't correct
8	Incorrect	0 ms	348 KB	Output isn't correct
9	Incorrect	0 ms	464 KB	Output isn't correct
10	Incorrect	1 ms	604 KB	Output isn't correct
11	Incorrect	1 ms	348 KB	Output isn't correct
12	Incorrect	1 ms	604 KB	Output isn't correct
13	Incorrect	1 ms	632 KB	Output isn't correct
14	Incorrect	1 ms	604 KB	Output isn't correct
15	Incorrect	2 ms	828 KB	Output isn't correct
16	Incorrect	2 ms	860 KB	Output isn't correct
17	Incorrect	3 ms	860 KB	Output isn't correct
18	Incorrect	2 ms	604 KB	Output isn't correct

Subtask #2

2.1875 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	860 KB	Output isn't correct
2	Incorrect	13 ms	3676 KB	Output isn't correct
3	Incorrect	132 ms	34048 KB	Output isn't correct
4	Incorrect	35 ms	8280 KB	Output isn't correct
5	Incorrect	74 ms	19284 KB	Output isn't correct
6	Incorrect	129 ms	33876 KB	Output isn't correct
7	Incorrect	1 ms	856 KB	Output isn't correct
8	Incorrect	1 ms	972 KB	Output isn't correct
9	Incorrect	1 ms	348 KB	Output isn't correct
10	Incorrect	1 ms	348 KB	Output isn't correct
11	Incorrect	1 ms	860 KB	Output isn't correct
12	Incorrect	0 ms	508 KB	Output isn't correct
13	Incorrect	13 ms	3808 KB	Output isn't correct
14	Incorrect	13 ms	2256 KB	Output isn't correct
15	Incorrect	9 ms	2632 KB	Output isn't correct
16	Incorrect	5 ms	1628 KB	Output isn't correct
17	Incorrect	32 ms	8964 KB	Output isn't correct
18	Incorrect	34 ms	8788 KB	Output isn't correct
19	Incorrect	30 ms	8284 KB	Output isn't correct
20	Incorrect	27 ms	7764 KB	Output isn't correct
21	Incorrect	74 ms	20068 KB	Output isn't correct
22	Incorrect	73 ms	19280 KB	Output isn't correct
23	Incorrect	64 ms	16568 KB	Output isn't correct
24	Incorrect	73 ms	19540 KB	Output isn't correct
25	Incorrect	118 ms	33872 KB	Output isn't correct
26	Correct	95 ms	26196 KB	Output is correct
27	Incorrect	139 ms	33924 KB	Output isn't correct
28	Incorrect	126 ms	33876 KB	Output isn't correct
29	Incorrect	135 ms	33876 KB	Output isn't correct
30	Incorrect	122 ms	33200 KB	Output isn't correct
31	Incorrect	82 ms	21844 KB	Output isn't correct
32	Incorrect	127 ms	34056 KB	Output isn't correct