Submission #646832

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
646832	2022-09-30T20:32:15 Z	beaconmc	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1200 ms	257288 KB

tracks

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)

bool visited[4001][4001];
char grid[4001][4001];
ll depth[4001][4001];

vector<ll> xx = {-1,1,0,0}, yy = {0,0,-1,1};

int main(){
	FOR(i,0,4001){
		FOR(j,0,4001){
			visited[i][j] = 0;
			grid[i][j] = 0;
			depth[i][j] = 0;
		}
	}
	ll n,m;
	cin >> n >> m;
	FOR(i,0,n){
		string temp;
		cin >> temp;
		FOR(j,0,m){
			grid[i][j] = temp[j];
		}
	}
	vector<char> ani;

	if (grid[0][0] == 'F'){
		ani = {'F','R'};
	}else ani = {'R','F'};

	deque<pair<ll,ll>> q;
	q.push_front(make_pair(0,0));

	while (q.size()){
		pair<ll,ll> node = q.front();
		q.pop_front();

		FOR(i,0,4){
			ll x = node.first + xx[i];
			ll y = node.second + yy[i];

			if (0<=x && x<n && 0<=y && y<m && grid[x][y] != '.'){
				if (grid[x][y] == ani[depth[node.first][node.second]%2] && !visited[x][y]){
					visited[x][y] = 1;
					depth[x][y] = depth[node.first][node.second];
					q.push_front(make_pair(x,y));
				}

				if (grid[x][y] != ani[depth[node.first][node.second]%2] && !visited[x][y]){
					depth[x][y] = depth[node.first][node.second]+1;
					visited[x][y] = 1;
					q.push_back(make_pair(x,y));
				}
			}
		}
	}
	ll maxi = -1;

	FOR(i,0,4001){
		FOR(j,0,4001){
			maxi = max(maxi, depth[i][j]);
		}
	}
	cout << maxi+1;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	93 ms	157032 KB	Output is correct
2	Correct	74 ms	156916 KB	Output is correct
3	Correct	77 ms	156980 KB	Output is correct
4	Correct	87 ms	157344 KB	Output is correct
5	Correct	81 ms	156892 KB	Output is correct
6	Correct	73 ms	156840 KB	Output is correct
7	Correct	73 ms	156888 KB	Output is correct
8	Correct	72 ms	156876 KB	Output is correct
9	Correct	73 ms	156920 KB	Output is correct
10	Correct	76 ms	156896 KB	Output is correct
11	Correct	76 ms	156976 KB	Output is correct
12	Correct	101 ms	156888 KB	Output is correct
13	Correct	84 ms	156816 KB	Output is correct
14	Correct	78 ms	156844 KB	Output is correct
15	Correct	86 ms	156896 KB	Output is correct
16	Correct	92 ms	157032 KB	Output is correct
17	Correct	91 ms	156860 KB	Output is correct
18	Correct	86 ms	157344 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	76 ms	156908 KB	Output is correct
2	Correct	137 ms	156876 KB	Output is correct
3	Correct	554 ms	157128 KB	Output is correct
4	Correct	186 ms	156876 KB	Output is correct
5	Correct	341 ms	156968 KB	Output is correct
6	Correct	1067 ms	183340 KB	Output is correct
7	Correct	87 ms	156904 KB	Output is correct
8	Correct	76 ms	156900 KB	Output is correct
9	Correct	76 ms	156876 KB	Output is correct
10	Correct	76 ms	156932 KB	Output is correct
11	Correct	80 ms	156908 KB	Output is correct
12	Correct	91 ms	156908 KB	Output is correct
13	Correct	143 ms	157008 KB	Output is correct
14	Correct	121 ms	156916 KB	Output is correct
15	Correct	108 ms	156800 KB	Output is correct
16	Correct	107 ms	156832 KB	Output is correct
17	Correct	244 ms	157028 KB	Output is correct
18	Correct	214 ms	156916 KB	Output is correct
19	Correct	195 ms	156920 KB	Output is correct
20	Correct	175 ms	156920 KB	Output is correct
21	Correct	355 ms	156992 KB	Output is correct
22	Correct	319 ms	156920 KB	Output is correct
23	Correct	414 ms	156940 KB	Output is correct
24	Correct	327 ms	156840 KB	Output is correct
25	Correct	723 ms	156924 KB	Output is correct
26	Correct	764 ms	257288 KB	Output is correct
27	Correct	878 ms	191848 KB	Output is correct
28	Correct	1080 ms	183316 KB	Output is correct
29	Correct	1200 ms	184016 KB	Output is correct
30	Correct	989 ms	186252 KB	Output is correct
31	Correct	927 ms	157816 KB	Output is correct
32	Correct	809 ms	187852 KB	Output is correct