oj.uz

답안 #855413

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
855413 2023-10-01T08:30:57 Z dayalk Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 591 ms 122016 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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