Submission #698857

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
698857	2023-02-14T13:46:41 Z	Azther0z	Tracks in the Snow (BOI13_tracks)	C++11	100 / 100	927 ms	130980 KB

tracks

#include <bits/stdc++.h>
using namespace std;
int n,m;
char grid[4001][4001];
int dist[4001][4001];
int di[]={0,0,1,-1};
int dj[]={1,-1,0,0};
int result=0;
bool valid(int i,int j)
{
	return 0<=i&&i<n&&0<=j&&j<m&&grid[i][j]!='.'&&dist[i][j]==0;
}
void bfs(int i,int j)
{
	deque<pair<int,int>> dq;
	dq.push_front({i,j});
	dist[i][j]=1;
	while(!dq.empty())
	{
		int ci=dq.front().first;
		int cj=dq.front().second;
		dq.pop_front();
		result=max(result,dist[ci][cj]);
		for(int k=0;k<4;k++)
		{
			int ni=ci+di[k];
			int nj=cj+dj[k];
			if(valid(ni,nj))
			{
				if(grid[ci][cj]==grid[ni][nj])
				{
					dq.push_front({ni,nj});
					dist[ni][nj]=dist[ci][cj];
				}
				else
				{
					dq.push_back({ni,nj});
					dist[ni][nj]=dist[ci][cj]+1;
				}
			}
		}
	}
}
int main()
{
	cin >> n >> m;
	for(int i=0;i<n;i++)
		cin >> grid[i];
	bfs(0,0);
	cout << result;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	5404 KB	Output is correct
2	Correct	1 ms	440 KB	Output is correct
3	Correct	1 ms	596 KB	Output is correct
4	Correct	10 ms	5184 KB	Output is correct
5	Correct	4 ms	2900 KB	Output is correct
6	Correct	0 ms	468 KB	Output is correct
7	Correct	1 ms	596 KB	Output is correct
8	Correct	1 ms	724 KB	Output is correct
9	Correct	1 ms	1084 KB	Output is correct
10	Correct	4 ms	2388 KB	Output is correct
11	Correct	3 ms	2132 KB	Output is correct
12	Correct	7 ms	3036 KB	Output is correct
13	Correct	4 ms	2876 KB	Output is correct
14	Correct	4 ms	2860 KB	Output is correct
15	Correct	14 ms	5204 KB	Output is correct
16	Correct	15 ms	5384 KB	Output is correct
17	Correct	12 ms	5128 KB	Output is correct
18	Correct	10 ms	5092 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	30812 KB	Output is correct
2	Correct	63 ms	15032 KB	Output is correct
3	Correct	441 ms	73364 KB	Output is correct
4	Correct	122 ms	32588 KB	Output is correct
5	Correct	280 ms	53264 KB	Output is correct
6	Correct	905 ms	107460 KB	Output is correct
7	Correct	18 ms	32140 KB	Output is correct
8	Correct	16 ms	30784 KB	Output is correct
9	Correct	3 ms	576 KB	Output is correct
10	Correct	1 ms	316 KB	Output is correct
11	Correct	16 ms	31572 KB	Output is correct
12	Correct	2 ms	1492 KB	Output is correct
13	Correct	63 ms	15008 KB	Output is correct
14	Correct	40 ms	10268 KB	Output is correct
15	Correct	37 ms	12968 KB	Output is correct
16	Correct	28 ms	5692 KB	Output is correct
17	Correct	158 ms	28624 KB	Output is correct
18	Correct	141 ms	35636 KB	Output is correct
19	Correct	117 ms	32652 KB	Output is correct
20	Correct	101 ms	25544 KB	Output is correct
21	Correct	280 ms	52568 KB	Output is correct
22	Correct	266 ms	53500 KB	Output is correct
23	Correct	306 ms	43728 KB	Output is correct
24	Correct	265 ms	49732 KB	Output is correct
25	Correct	620 ms	94148 KB	Output is correct
26	Correct	927 ms	130980 KB	Output is correct
27	Correct	878 ms	112576 KB	Output is correct
28	Correct	892 ms	107564 KB	Output is correct
29	Correct	924 ms	105200 KB	Output is correct
30	Correct	903 ms	109772 KB	Output is correct
31	Correct	751 ms	73424 KB	Output is correct
32	Correct	911 ms	110564 KB	Output is correct