Submission #781114

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
781114	2023-07-12T18:06:32 Z	hasan_tawsif	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	673 ms	130936 KB

tracks

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int inf = (int) 1e9;

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

char adj[4002][4002];
int dis[4002][4002];

void solve() {
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j) cin >> adj[i][j], dis[i][j] = inf;
	deque<pair<int , int > > dq;
	dq.push_front({1, 1});
	dis[1][1] = 1;

	auto valid = [&] (int r, int c) {
		return r >= 1 and r <= n and c >= 1 and c <= m and adj[r][c] != '.';
	};

	int ans = 0;

	while (!dq.empty()) {
		auto [r, c] = dq.front(); dq.pop_front();
		ans = max(ans, dis[r][c]);
		//cerr << r << " " << c << endl;
		for (int i = 0; i < 4; ++i) {
			int nr = dx[i] + r, nc = dy[i] + c;
			if (!valid(nr, nc)) continue;
			int wt;
			if (adj[nr][nc] == adj[r][c]) {
				wt = 0;
			} else wt = 1;
			if (dis[r][c] + wt < dis[nr][nc]) {
				dis[nr][nc] = wt + dis[r][c];
				if (wt == 0) dq.push_front({nr, nc});
				else dq.push_back({nr, nc});
			}
		}
	}
	cout << ans << "\n";
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1; 
//    cin >> t;
    while(t--) solve();
}

Compilation message

tracks.cpp: In function 'void solve()':
tracks.cpp:29:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |   auto [r, c] = dq.front(); dq.pop_front();
      |        ^

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	5460 KB	Output is correct
2	Correct	1 ms	468 KB	Output is correct
3	Correct	1 ms	716 KB	Output is correct
4	Correct	8 ms	5204 KB	Output is correct
5	Correct	3 ms	3028 KB	Output is correct
6	Correct	0 ms	468 KB	Output is correct
7	Correct	1 ms	724 KB	Output is correct
8	Correct	1 ms	724 KB	Output is correct
9	Correct	1 ms	1108 KB	Output is correct
10	Correct	3 ms	2644 KB	Output is correct
11	Correct	3 ms	2128 KB	Output is correct
12	Correct	6 ms	3116 KB	Output is correct
13	Correct	3 ms	3028 KB	Output is correct
14	Correct	3 ms	3028 KB	Output is correct
15	Correct	12 ms	5504 KB	Output is correct
16	Correct	14 ms	5472 KB	Output is correct
17	Correct	9 ms	5204 KB	Output is correct
18	Correct	8 ms	5204 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	30908 KB	Output is correct
2	Correct	45 ms	17824 KB	Output is correct
3	Correct	287 ms	94308 KB	Output is correct
4	Correct	76 ms	33612 KB	Output is correct
5	Correct	197 ms	67864 KB	Output is correct
6	Correct	656 ms	108564 KB	Output is correct
7	Correct	16 ms	32224 KB	Output is correct
8	Correct	17 ms	30936 KB	Output is correct
9	Correct	3 ms	724 KB	Output is correct
10	Correct	1 ms	468 KB	Output is correct
11	Correct	14 ms	31640 KB	Output is correct
12	Correct	1 ms	1616 KB	Output is correct
13	Correct	50 ms	17916 KB	Output is correct
14	Correct	30 ms	11904 KB	Output is correct
15	Correct	25 ms	13032 KB	Output is correct
16	Correct	24 ms	6648 KB	Output is correct
17	Correct	140 ms	36064 KB	Output is correct
18	Correct	94 ms	35768 KB	Output is correct
19	Correct	77 ms	33612 KB	Output is correct
20	Correct	68 ms	31080 KB	Output is correct
21	Correct	192 ms	70104 KB	Output is correct
22	Correct	156 ms	67868 KB	Output is correct
23	Correct	231 ms	56900 KB	Output is correct
24	Correct	176 ms	69512 KB	Output is correct
25	Correct	453 ms	94304 KB	Output is correct
26	Correct	436 ms	130936 KB	Output is correct
27	Correct	575 ms	107824 KB	Output is correct
28	Correct	658 ms	108520 KB	Output is correct
29	Correct	673 ms	106660 KB	Output is correct
30	Correct	628 ms	107944 KB	Output is correct
31	Correct	564 ms	73464 KB	Output is correct
32	Correct	476 ms	108768 KB	Output is correct