Submission #849355

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
849355	2023-09-14T14:10:59 Z	Artteiv	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1311 ms	69440 KB

tracks

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
#define pll pair<long long,long long>
#define int long long
#define pii pair<int,int>
#define FOR(i,a,b) for(int i =a; i<=b; i++)
#define ROF(i,a,b) for(int i =a; i>=b; i--)

const long long MOD = 1e9+7;

using namespace std;

vector<vector<bool>> stat;
vector<string> s;
int cur;
int w,h; 
int cn = 0;
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
bool ok(pii a){
	if (a.first<=h && a.first>=1 
		&& a.second<=w && a.second>=1 
		&& stat[a.first][a.second]==0) 
		return 1;
	return 0;
}
int nx(int c){
	if (c=='F') return 'R';
	return 'F';
}
void solve(){
	cin>>h>>w;
	s.resize(h+1);
	stat.resize(h+1);
	for (int i =1; i<=h; i++){
		stat[i].resize(w+1);
		cin>>s[i];
		s[i] = '#'+s[i];
	}	
	cur = s[1][1];
	bool msk = 0;
	deque<pii> bfs[2];
	bfs[msk].push_back({1,1});
	int res=0;
	while (bfs[msk].size()){
		auto [x,y] = bfs[msk].front();
		bfs[msk].pop_front();
		if (stat[x][y]){
			if (bfs[msk].empty()){
				res++;
				msk = !msk;
				cur = nx(cur);
			}
			continue;
		}
		stat[x][y]=1;
		for (int i =0; i<4; i++){
			int X = x+dx[i],Y = y+dy[i];
			if (ok({X,Y})){
				if(s[X][Y]==nx(cur)){
					bfs[!msk].push_back({X,Y});
				}
				else if (s[X][Y]==cur){
					bfs[msk].push_back({X,Y});
				}
			}
		}
		if (bfs[msk].empty()){
			res++;
			msk = !msk;
			cur = nx(cur);
		}
	}	
	cout<<res<<endl;
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
		solve();
	return 0;
}

Compilation message

tracks.cpp: In function 'void solve()':
tracks.cpp:47:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |   auto [x,y] = bfs[msk].front();
      |        ^

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	1116 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	10 ms	1112 KB	Output is correct
5	Correct	2 ms	600 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	2 ms	468 KB	Output is correct
11	Correct	3 ms	708 KB	Output is correct
12	Correct	7 ms	604 KB	Output is correct
13	Correct	2 ms	604 KB	Output is correct
14	Correct	2 ms	604 KB	Output is correct
15	Correct	15 ms	1128 KB	Output is correct
16	Correct	19 ms	1116 KB	Output is correct
17	Correct	9 ms	1108 KB	Output is correct
18	Correct	10 ms	1116 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	860 KB	Output is correct
2	Correct	54 ms	3916 KB	Output is correct
3	Correct	224 ms	34200 KB	Output is correct
4	Correct	52 ms	8784 KB	Output is correct
5	Correct	129 ms	19536 KB	Output is correct
6	Correct	1297 ms	69392 KB	Output is correct
7	Correct	2 ms	856 KB	Output is correct
8	Correct	2 ms	856 KB	Output is correct
9	Correct	2 ms	604 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	1 ms	724 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	53 ms	3916 KB	Output is correct
14	Correct	30 ms	2396 KB	Output is correct
15	Correct	12 ms	2708 KB	Output is correct
16	Correct	32 ms	1900 KB	Output is correct
17	Correct	138 ms	9280 KB	Output is correct
18	Correct	45 ms	9044 KB	Output is correct
19	Correct	44 ms	8428 KB	Output is correct
20	Correct	54 ms	7772 KB	Output is correct
21	Correct	137 ms	20276 KB	Output is correct
22	Correct	126 ms	19620 KB	Output is correct
23	Correct	282 ms	17076 KB	Output is correct
24	Correct	112 ms	19972 KB	Output is correct
25	Correct	279 ms	34252 KB	Output is correct
26	Correct	656 ms	26580 KB	Output is correct
27	Correct	884 ms	40776 KB	Output is correct
28	Correct	1311 ms	69440 KB	Output is correct
29	Correct	1226 ms	62000 KB	Output is correct
30	Correct	1070 ms	60720 KB	Output is correct
31	Correct	1018 ms	23972 KB	Output is correct
32	Correct	788 ms	38740 KB	Output is correct