Submission #905060

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
905060	2024-01-12T13:35:12 Z	pete555	Tracks in the Snow (BOI13_tracks)	C++17	89.0625 / 100	1803 ms	286688 KB

tracks

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

const int dx[]{0,1,0,-1};
const int dy[]{1,0,-1,0};

bool in(int x, int y, int n, int m) {
	return (x > -1 && x < n && y > -1 && y < m);
}

int main()
{
	int n, m;
	cin >> n >> m;
	char md[n][m];
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++)
			cin >> md[i][j];
	bool vis[n][m]{};
	int d[n][m];
	d[0][0] = 1;
	int ans = 1;
	deque<pair<int,int>> q;
	q.push_front({0,0});
	while(!q.empty()){
		int x=q.front().first;
		int y=q.front().second;
		q.pop_front();
		if(vis[x][y]) continue;
		vis[x][y] = true;
		ans = max(ans, d[x][y]);
		for(int i=0; i<4; i++){
			if(md[x+dx[i]][y+dy[i]] == md[x][y] 
			and in(x+dx[i], y+dy[i], n, m)){
				d[x+dx[i]][y+dy[i]] = d[x][y];
				q.push_front({x+dx[i], y+dy[i]});
			}else{
				if(md[x+dx[i]][y+dy[i]] == '.') continue;
				if(in(x+dx[i], y+dy[i], n, m)){
					d[x+dx[i]][y+dy[i]] = d[x][y]+1;
					q.push_back({x+dx[i], y+dy[i]});
				}
			}	
		}
	}
	cout << ans << '\n';
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	2164 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	600 KB	Output is correct
4	Correct	14 ms	1884 KB	Output is correct
5	Correct	6 ms	860 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	444 KB	Output is correct
9	Correct	1 ms	440 KB	Output is correct
10	Correct	4 ms	860 KB	Output is correct
11	Correct	4 ms	860 KB	Output is correct
12	Correct	8 ms	1116 KB	Output is correct
13	Correct	4 ms	1012 KB	Output is correct
14	Correct	6 ms	860 KB	Output is correct
15	Correct	24 ms	2140 KB	Output is correct
16	Correct	25 ms	2140 KB	Output is correct
17	Correct	15 ms	2136 KB	Output is correct
18	Correct	14 ms	1884 KB	Output is correct

Subtask #2

59.0625 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	716 KB	Output is correct
2	Correct	102 ms	11132 KB	Output is correct
3	Runtime error	672 ms	206664 KB	Execution killed with signal 11
4	Correct	175 ms	26120 KB	Output is correct
5	Correct	410 ms	62060 KB	Output is correct
6	Correct	1800 ms	144624 KB	Output is correct
7	Correct	3 ms	604 KB	Output is correct
8	Correct	4 ms	604 KB	Output is correct
9	Runtime error	5 ms	1372 KB	Execution killed with signal 11
10	Runtime error	2 ms	860 KB	Execution killed with signal 11
11	Correct	3 ms	604 KB	Output is correct
12	Correct	2 ms	348 KB	Output is correct
13	Correct	96 ms	11168 KB	Output is correct
14	Correct	53 ms	6620 KB	Output is correct
15	Correct	63 ms	7372 KB	Output is correct
16	Correct	45 ms	4696 KB	Output is correct
17	Correct	230 ms	28268 KB	Output is correct
18	Correct	201 ms	27600 KB	Output is correct
19	Correct	184 ms	25952 KB	Output is correct
20	Correct	177 ms	23976 KB	Output is correct
21	Correct	443 ms	64048 KB	Output is correct
22	Correct	432 ms	62036 KB	Output is correct
23	Correct	497 ms	53332 KB	Output is correct
24	Correct	395 ms	62548 KB	Output is correct
25	Correct	936 ms	110420 KB	Output is correct
26	Correct	1649 ms	286688 KB	Output is correct
27	Runtime error	820 ms	273664 KB	Execution killed with signal 11
28	Correct	1803 ms	144868 KB	Output is correct
29	Correct	1774 ms	143612 KB	Output is correct
30	Correct	1651 ms	164236 KB	Output is correct
31	Runtime error	411 ms	133460 KB	Execution killed with signal 11
32	Correct	1581 ms	202892 KB	Output is correct