Submission #499005

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
499005	2021-12-27T02:58:07 Z	vbee	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	761 ms	238576 KB

tracks

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define ii pair<int,int>
#define vii vector<ii>
#define vi vector<int>
#define fi first
#define se second
#define TASK ""
#define ll long long
#define pll pair<ll, ll>
#define vll vector<ll>
#define vpll vector<pll>
#define pb push_back
#define MASK(i) (1 << (i))
#define BIT(x, i) ((x >> (i)) & 1)
 
using namespace std;

const int oo = 1e9 + 7;
const ll loo = (ll)1e18 + 7;
const int N = 4e3 + 7; 
ll n, m, dist[N][N];
char a[N][N];
bool visited[N][N];
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
bool check(ll i, ll j){
	if (i < 1 || j < 1 || i > n || j > m || a[i][j] == '.' || visited[i][j]) return false;
	return true;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	//freopen(TASK".in", "r", stdin);
	//freopen(TASK".out", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			cin >> a[i][j];
		}
	}
	deque<pll> kew;
	kew.push_back({1, 1});
	visited[1][1] = true;
	ll res = 0;
	while (!kew.empty()){
		auto k = kew.front();
		kew.pop_front();
		res = max(res, dist[k.fi][k.se]);
		for (int i = 0; i < 4; i++){
			ll newx = k.fi + dx[i];
			ll newy = k.se + dy[i];
			if (check(newx, newy)){
				visited[newx][newy] = true;
				dist[newx][newy] = dist[k.fi][k.se];
				if (a[k.fi][k.se] == a[newx][newy]){
					kew.push_front({newx, newy});
				}
				else {
					dist[newx][newy]++;
					kew.push_back({newx, newy});
				}
			}
		}
	}
	cout << res + 1;
	return 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	8252 KB	Output is correct
2	Correct	1 ms	432 KB	Output is correct
3	Correct	1 ms	832 KB	Output is correct
4	Correct	10 ms	7880 KB	Output is correct
5	Correct	4 ms	4304 KB	Output is correct
6	Correct	1 ms	460 KB	Output is correct
7	Correct	1 ms	844 KB	Output is correct
8	Correct	1 ms	1100 KB	Output is correct
9	Correct	1 ms	1472 KB	Output is correct
10	Correct	5 ms	3528 KB	Output is correct
11	Correct	3 ms	3136 KB	Output is correct
12	Correct	7 ms	4556 KB	Output is correct
13	Correct	6 ms	4300 KB	Output is correct
14	Correct	4 ms	4288 KB	Output is correct
15	Correct	13 ms	7920 KB	Output is correct
16	Correct	15 ms	8344 KB	Output is correct
17	Correct	11 ms	8008 KB	Output is correct
18	Correct	9 ms	7884 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	19 ms	46024 KB	Output is correct
2	Correct	56 ms	22280 KB	Output is correct
3	Correct	334 ms	91852 KB	Output is correct
4	Correct	105 ms	50920 KB	Output is correct
5	Correct	264 ms	74860 KB	Output is correct
6	Correct	761 ms	184000 KB	Output is correct
7	Correct	32 ms	48024 KB	Output is correct
8	Correct	22 ms	46004 KB	Output is correct
9	Correct	2 ms	844 KB	Output is correct
10	Correct	1 ms	460 KB	Output is correct
11	Correct	22 ms	47180 KB	Output is correct
12	Correct	2 ms	2252 KB	Output is correct
13	Correct	57 ms	22316 KB	Output is correct
14	Correct	47 ms	15904 KB	Output is correct
15	Correct	35 ms	20676 KB	Output is correct
16	Correct	24 ms	8772 KB	Output is correct
17	Correct	133 ms	41092 KB	Output is correct
18	Correct	117 ms	55936 KB	Output is correct
19	Correct	101 ms	50928 KB	Output is correct
20	Correct	80 ms	34600 KB	Output is correct
21	Correct	197 ms	66768 KB	Output is correct
22	Correct	236 ms	74816 KB	Output is correct
23	Correct	247 ms	60356 KB	Output is correct
24	Correct	216 ms	65740 KB	Output is correct
25	Correct	558 ms	157892 KB	Output is correct
26	Correct	505 ms	238576 KB	Output is correct
27	Correct	652 ms	192936 KB	Output is correct
28	Correct	759 ms	184232 KB	Output is correct
29	Correct	753 ms	184736 KB	Output is correct
30	Correct	688 ms	183940 KB	Output is correct
31	Correct	607 ms	120020 KB	Output is correct
32	Correct	588 ms	181944 KB	Output is correct