Submission #915112

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
915112	2024-01-23T11:13:55 Z	Trytytka	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	871 ms	106960 KB

tracks

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

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int h, w;
	cin >> h >> w;
	vector<string> a(h);
	for (int i = 0; i < h; i++){
		cin >> a[i];
	}
	vector<vector<int>> b(h, vector<int>(w));
	queue<pair<int, int>> q;
	queue<pair<int, int>> p;
	q.push({0, 0});
	b[0][0]=1;
	int x, y;
	int s=0;
	while(q.size()){
		while(q.size()){
			x=q.front().first;
			y=q.front().second;
			q.pop();
			if(y-1>=0){
				if(b[x][y-1]==0){
					if(a[x][y-1]==a[x][y]) {q.push({x, y-1}); b[x][y-1]=1;}
					else if(a[x][y-1]!='.') {p.push({x, y-1}); b[x][y-1]=1;}
				}
			}
			if(y+1<w){
				if(b[x][y+1]==0){
					if(a[x][y+1]==a[x][y]) {q.push({x, y+1}); b[x][y+1]=1;}
					else if(a[x][y+1]!='.')  {p.push({x, y+1}); b[x][y+1]=1;}
				}
			}
			if(x-1>=0){
				if(b[x-1][y]==0){
					if(a[x-1][y]==a[x][y]) {q.push({x-1, y}); b[x-1][y]=1;}
					else if(a[x-1][y]!='.') {p.push({x-1, y}); b[x-1][y]=1;}
				}
			}
			if(x+1<h){
				if(b[x+1][y]==0){
					if(a[x+1][y]==a[x][y]) {q.push({x+1, y}); b[x+1][y]=1;}
					else if(a[x+1][y]!='.')  {p.push({x+1, y}); b[x+1][y]=1;}
				}
			}
		}
		swap(q, p);
		s++;
	}
	cout << s;
}

Subtask #1

30.0 / 30.0

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

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	724 KB	Output is correct
2	Correct	29 ms	9820 KB	Output is correct
3	Correct	167 ms	96660 KB	Output is correct
4	Correct	48 ms	22612 KB	Output is correct
5	Correct	112 ms	54408 KB	Output is correct
6	Correct	848 ms	106960 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	604 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	856 KB	Output is correct
12	Correct	1 ms	604 KB	Output is correct
13	Correct	29 ms	9820 KB	Output is correct
14	Correct	18 ms	5720 KB	Output is correct
15	Correct	11 ms	6236 KB	Output is correct
16	Correct	14 ms	4188 KB	Output is correct
17	Correct	102 ms	24704 KB	Output is correct
18	Correct	43 ms	24132 KB	Output is correct
19	Correct	49 ms	22864 KB	Output is correct
20	Correct	37 ms	21036 KB	Output is correct
21	Correct	95 ms	56160 KB	Output is correct
22	Correct	111 ms	54156 KB	Output is correct
23	Correct	196 ms	46676 KB	Output is correct
24	Correct	97 ms	54876 KB	Output is correct
25	Correct	431 ms	96656 KB	Output is correct
26	Correct	335 ms	74000 KB	Output is correct
27	Correct	479 ms	98184 KB	Output is correct
28	Correct	871 ms	106272 KB	Output is correct
29	Correct	760 ms	105212 KB	Output is correct
30	Correct	611 ms	102324 KB	Output is correct
31	Correct	480 ms	62120 KB	Output is correct
32	Correct	431 ms	97440 KB	Output is correct