Submission #855413

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
855413	2023-10-01T08:30:57 Z	dayalk	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	591 ms	122016 KB

tracks

#include <bits/stdc++.h>
#define mod 1000000007
#define init(arr, val) memset(arr, val, sizeof(arr))
#define fr(a,b) for(ll i = a; i < b; i++)
#define loop(i, a, b) for (ll i = a; i < b; i++)
#define loopr(i, a, b) for (ll i = a; i >= b; i--)
#define loops(i, a, b, step) for (ll i = a; i < b; i += step)
#define looprs(i, a, b, step) for (ll i = a; i >= b; i -= step)
#define ull unsigned long long int
#define ll long long int
#define P pair
#define pll pair<long long, long long>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define PUU pair<unsigned long long int, unsigned long long int>
#define L list
#define V vector
#define D deque
#define ST set
#define MS multiset
#define M map
#define UM unordered_map
#define mp make_pair
#define pb push_back
#define pf push_front
#define MM multimap
#define F first
#define S second
#define IT iterator
#define RIT reverse_iterator
#define fast_io                       \
	ios_base::sync_with_stdio(false); \
	cin.tie();                        \
	cout.tie()
#define FILE_READ_IN freopen("input.txt", "r", stdin);
#define FILE_READ_OUT freopen("output.txt", "w", stdout);
#define prDouble(x) cout << fixed << setprecision(10) << x
#define all(a) a.begin(), a.end()
#define ld long double
#define inf (1LL<<60)
using namespace std;
const ll maxn = 2e5 + 1;
const double pi = acos(-1);

vector<pii> dir = { {1,0}, {0,1}, {0, -1}, {-1, 0} };

int main() {
	fast_io;
	int tests = 1;
	// cin >> tests;
	for (int test_case = 1; test_case <= tests; test_case++) {
		int h, w; cin >> h >> w;
		char a[h][w];
		fr(0, h) {
			loop(j, 0, w) cin >> a[i][j];
		}
		vector<int> d(h * w, 1e9);
		d[0] = 1;
		deque<pair<int, int>> q;
		q.push_back(make_pair(0, 0));
		int res = 0;
		while (!q.empty()) {
			auto cur = q.front();
			int curf = cur.first;
			int curs = cur.second;
			q.pop_front();
			auto dis = d[curf * w + curs];
			res = max(res, dis);
			for (auto i : dir) {
				// pii j = cur + i;
				int jf = curf + i.first;
				int js = curs + i.second;
				if (jf < 0) continue;
				if (jf >= h) continue;
				if (js < 0) continue;
				if (js >= w) continue;
				if (a[jf][js] == '.') continue;
				int e = 0;
				// if (a[curf][curs] != '.') {
				e = (a[curf][curs] != a[jf][js]);
				// }
				if (dis + e < d[jf * w + js]) {
					d[jf * w + js] = dis + e;
					if (e == 0) q.push_front({ jf,js });
					else q.push_back({ jf,js });
				}
			}
		}
		// fr(0, h * w) {
		// 	if (a[i / w][i % w]) res = max(res, d[i]);
		// }
		cout << res << endl;
	}
	return 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	1628 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	6 ms	1372 KB	Output is correct
5	Correct	2 ms	860 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	2 ms	788 KB	Output is correct
11	Correct	2 ms	604 KB	Output is correct
12	Correct	5 ms	860 KB	Output is correct
13	Correct	3 ms	860 KB	Output is correct
14	Correct	2 ms	860 KB	Output is correct
15	Correct	9 ms	1628 KB	Output is correct
16	Correct	11 ms	1628 KB	Output is correct
17	Correct	8 ms	1448 KB	Output is correct
18	Correct	6 ms	1372 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	604 KB	Output is correct
2	Correct	45 ms	8116 KB	Output is correct
3	Correct	290 ms	78924 KB	Output is correct
4	Correct	77 ms	18704 KB	Output is correct
5	Correct	191 ms	44372 KB	Output is correct
6	Correct	591 ms	93384 KB	Output is correct
7	Correct	1 ms	604 KB	Output is correct
8	Correct	1 ms	612 KB	Output is correct
9	Correct	2 ms	604 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	600 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	40 ms	8028 KB	Output is correct
14	Correct	24 ms	4880 KB	Output is correct
15	Correct	21 ms	5212 KB	Output is correct
16	Correct	19 ms	3420 KB	Output is correct
17	Correct	102 ms	20308 KB	Output is correct
18	Correct	79 ms	19960 KB	Output is correct
19	Correct	72 ms	18772 KB	Output is correct
20	Correct	75 ms	17120 KB	Output is correct
21	Correct	172 ms	45900 KB	Output is correct
22	Correct	190 ms	44320 KB	Output is correct
23	Correct	201 ms	38372 KB	Output is correct
24	Correct	173 ms	45140 KB	Output is correct
25	Correct	407 ms	78716 KB	Output is correct
26	Correct	346 ms	110560 KB	Output is correct
27	Correct	518 ms	122016 KB	Output is correct
28	Correct	583 ms	93296 KB	Output is correct
29	Correct	577 ms	90472 KB	Output is correct
30	Correct	544 ms	96952 KB	Output is correct
31	Correct	407 ms	51020 KB	Output is correct
32	Correct	473 ms	101092 KB	Output is correct