Submission #360667

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
360667	2021-01-28T05:39:35 Z	ronnith	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	979 ms	155032 KB

tracks

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using tiii = tuple<int, int, int>;
using str = string;
using ld = long double;

#define FOR(i,a,b) for(int i = (a);i < (b);i ++)
#define ROF(i,a,b) for(int i = (a);i >= (b);i --)
#define For(i,b) for(int i = 0;i < (b);i ++)
#define Rof(i,b) for(int i = (b);i >= 0;i --)
#define trav(a, b) for(auto a : (b))

#define all(a) (a).begin(), (a).end()
#define sz(a) int((a).size())
#define lb(x, y) lower_bound(all(x), y) 
#define ub(x, y) upper_bound(all(x), y)
#define beg(x) (x).begin()
#define en(x) (x).end()
#define pb push_back
#define eb emplace_back
#define ins insert

#define mk make_pair
#define mt make_tuple
#define f first
#define s second

const int N = 4000;

int n, m;
int level[N][N];
char a[N][N];
deque<tiii> q;

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void bfs_01() {
	q.pb({0, 0, 0});
	level[0][0] = 0;
	while(sz(q)) {
		auto x = q.front();
		int d, i, j;tie(d, i, j) = x;
		q.pop_front();
		if(d != level[i][j]) continue;
		FOR(k,0,4) {
			int nx = i + dx[k], ny = j + dy[k];
			if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if(a[nx][ny] == '.') continue;
			if(level[nx][ny] > level[i][j] + (a[i][j] != a[nx][ny])) {
				level[nx][ny] = level[i][j] + (a[i][j] != a[nx][ny]);
				if(a[i][j] != a[nx][ny]) {
					q.pb({level[nx][ny], nx, ny});
				} else {
					q.push_front({level[nx][ny], nx, ny});
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m;
	For(i,n) {
		For(j,m) {
			cin >> a[i][j];
			level[i][j] = INT_MAX;
		}
	}

	bfs_01();

	int ans = 0;
	For(i,n) {
		For(j,m) {
			if(a[i][j] != '.') {
				ans = max(ans, level[i][j]);
			}
		}
	}

	cout << ans + 1 << '\n';

	return 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	5484 KB	Output is correct
2	Correct	1 ms	492 KB	Output is correct
3	Correct	1 ms	748 KB	Output is correct
4	Correct	10 ms	5228 KB	Output is correct
5	Correct	4 ms	3052 KB	Output is correct
6	Correct	1 ms	492 KB	Output is correct
7	Correct	1 ms	748 KB	Output is correct
8	Correct	1 ms	876 KB	Output is correct
9	Correct	1 ms	1132 KB	Output is correct
10	Correct	5 ms	2668 KB	Output is correct
11	Correct	3 ms	2284 KB	Output is correct
12	Correct	7 ms	3052 KB	Output is correct
13	Correct	5 ms	3052 KB	Output is correct
14	Correct	5 ms	3052 KB	Output is correct
15	Correct	15 ms	5484 KB	Output is correct
16	Correct	17 ms	5484 KB	Output is correct
17	Correct	19 ms	5228 KB	Output is correct
18	Correct	11 ms	5228 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	30700 KB	Output is correct
2	Correct	67 ms	17900 KB	Output is correct
3	Correct	441 ms	94316 KB	Output is correct
4	Correct	132 ms	33644 KB	Output is correct
5	Correct	289 ms	67820 KB	Output is correct
6	Correct	891 ms	114272 KB	Output is correct
7	Correct	21 ms	32108 KB	Output is correct
8	Correct	18 ms	30700 KB	Output is correct
9	Correct	3 ms	748 KB	Output is correct
10	Correct	1 ms	492 KB	Output is correct
11	Correct	19 ms	31596 KB	Output is correct
12	Correct	3 ms	1644 KB	Output is correct
13	Correct	67 ms	18028 KB	Output is correct
14	Correct	38 ms	11884 KB	Output is correct
15	Correct	40 ms	13164 KB	Output is correct
16	Correct	34 ms	6636 KB	Output is correct
17	Correct	172 ms	35948 KB	Output is correct
18	Correct	154 ms	35692 KB	Output is correct
19	Correct	135 ms	33516 KB	Output is correct
20	Correct	105 ms	31084 KB	Output is correct
21	Correct	267 ms	70124 KB	Output is correct
22	Correct	291 ms	67924 KB	Output is correct
23	Correct	323 ms	56940 KB	Output is correct
24	Correct	264 ms	69484 KB	Output is correct
25	Correct	703 ms	94320 KB	Output is correct
26	Correct	588 ms	155032 KB	Output is correct
27	Correct	773 ms	133712 KB	Output is correct
28	Correct	979 ms	114320 KB	Output is correct
29	Correct	880 ms	111952 KB	Output is correct
30	Correct	838 ms	118840 KB	Output is correct
31	Correct	700 ms	73820 KB	Output is correct
32	Correct	724 ms	116948 KB	Output is correct