Submission #747074

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
747074	2023-05-23T15:06:22 Z	LCJLY	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1078 ms	66652 KB

tracks

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

#define int long long 
typedef pair<int,int>pii;

int32_t main(){
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	int n,m;
	cin >> n >> m;
	
	string arr[n];
	for(int x=0;x<n;x++){
		cin >> arr[x];
	}
	
	queue<pii>q;
	queue<pii>q2;
	int counter=0;
	bool visited[n+5][m+5];
	memset(visited,0,sizeof(visited));
	
	bool amos=true;
	//true is R, false is F
	if(arr[0][0]=='F') amos=false;
	if(amos){
		q.push({0,0});
		visited[0][0]=true;
	}
	else{
		q2.push({0,0});
		visited[0][0]=true;
	}	
	
	pii dir[4]={
		{1,0},
		{-1,0},
		{0,1},
		{0,-1},
	};
	
	while(!q.empty()||!q2.empty()){
		if(amos){
			//cout << "true\n";
			while(!q.empty()){
				pii cur=q.front();
				q.pop();
				
				for(auto it:dir){
					int newx=cur.first+it.first;
					int newy=cur.second+it.second;
					if(newx<0||newy<0||newx>=n||newy>=m) continue;
					if(visited[newx][newy]) continue;
					if(arr[newx][newy]=='.') continue;
					visited[newx][newy]=true;
					if(arr[newx][newy]=='R'){
						q.push({newx,newy});
					}
					else{
						q2.push({newx,newy});
					}
				}	
			}
			amos=false;
		}
		else{
			//cout << "false\n";
			while(!q2.empty()){
				pii cur=q2.front();
				q2.pop();
				//cout << cur.first << " " << cur.second << " visit\n";
				for(auto it:dir){
					int newx=cur.first+it.first;
					int newy=cur.second+it.second;
					if(newx<0||newy<0||newx>=n||newy>=m) continue;
					if(visited[newx][newy]) continue;
					if(arr[newx][newy]=='.') continue;
					visited[newx][newy]=true;
					if(arr[newx][newy]=='R'){
						q.push({newx,newy});
					} 
					else{
						q2.push({newx,newy});
					}
				}	
			}
			amos=true;
		}
		counter++;
		//cout << counter << "\n";
	}
	cout << counter;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	1228 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	9 ms	872 KB	Output is correct
5	Correct	4 ms	468 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	3 ms	468 KB	Output is correct
11	Correct	3 ms	468 KB	Output is correct
12	Correct	5 ms	596 KB	Output is correct
13	Correct	4 ms	468 KB	Output is correct
14	Correct	3 ms	468 KB	Output is correct
15	Correct	13 ms	988 KB	Output is correct
16	Correct	14 ms	1108 KB	Output is correct
17	Correct	11 ms	1020 KB	Output is correct
18	Correct	8 ms	968 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	468 KB	Output is correct
2	Correct	61 ms	4224 KB	Output is correct
3	Correct	452 ms	46232 KB	Output is correct
4	Correct	130 ms	11120 KB	Output is correct
5	Correct	290 ms	20408 KB	Output is correct
6	Correct	1078 ms	66420 KB	Output is correct
7	Correct	2 ms	468 KB	Output is correct
8	Correct	3 ms	468 KB	Output is correct
9	Correct	3 ms	468 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	2 ms	416 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	73 ms	4256 KB	Output is correct
14	Correct	41 ms	2952 KB	Output is correct
15	Correct	33 ms	3184 KB	Output is correct
16	Correct	31 ms	1688 KB	Output is correct
17	Correct	179 ms	11996 KB	Output is correct
18	Correct	142 ms	11932 KB	Output is correct
19	Correct	117 ms	11148 KB	Output is correct
20	Correct	105 ms	10316 KB	Output is correct
21	Correct	291 ms	21208 KB	Output is correct
22	Correct	284 ms	20528 KB	Output is correct
23	Correct	364 ms	17356 KB	Output is correct
24	Correct	273 ms	21052 KB	Output is correct
25	Correct	624 ms	46224 KB	Output is correct
26	Correct	547 ms	25656 KB	Output is correct
27	Correct	773 ms	49620 KB	Output is correct
28	Correct	1061 ms	66652 KB	Output is correct
29	Correct	1025 ms	63460 KB	Output is correct
30	Correct	880 ms	61032 KB	Output is correct
31	Correct	705 ms	23464 KB	Output is correct
32	Correct	714 ms	47756 KB	Output is correct