답안 #1076900

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1076900	2024-08-26T18:29:53 Z	poconut	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	765 ms	222160 KB

tracks

#include"bits/stdc++.h"
#ifndef LOCAL
#define LINE
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);
#else
#define LINE cerr << "----------" << nl;
#define fastio
#endif
using namespace std;
using ll = long long; using ld = long double;
#define nl '\n'
#define arr array
#define pb push_back
#define S second
#define F first
#define int long long

const ll inf = 1e9+5;

void solve() {
	int n,m; cin >> n >> m;
	vector<string> a(n);
	for (int i=0; i<n; i++) {
		cin >> a[i];
	}
	deque<arr<int, 2>> q;
	vector dis(n, vector<int>(m, -1));
	int ans = 1;
	auto ok = [&] (int x, int y) {
		return x >=0 && x < n && y>=0 && y<m && dis[x][y] == -1 && a[x][y] != '.';
	};
	const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, -1, 1};
	dis[0][0] = 1;
	q.push_front({0,0});
	while (q.size()) {
		auto [x, y] = q.front();
		q.pop_front();
		for (int k=0; k<4; k++) {
			int xx = x+dx[k], yy = y+dy[k];
			if (ok(xx, yy)) {
				if (a[xx][yy]!=a[x][y]) {
					dis[xx][yy] = dis[x][y]+1;
					q.push_back({xx, yy});
				} else {
					dis[xx][yy] = dis[x][y];
					q.push_front({xx, yy});
				}
			}
		}
	}
	for (int i=0; i<n; i++) {
		for (int j=0; j<m; j++) {
			ans = max(ans, dis[i][j]);
		}
	}
	cout << ans << nl;
}

int32_t main() {
	/*
	freopen("swap.in", "r", stdin);
	freopen("swap.out", "w", stdout);
	*/
	int t = 1;
	//cin >> t;
	while (t--) {
		solve();
		LINE
	}
    return 0;
}

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	3164 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	7 ms	2396 KB	Output is correct
5	Correct	3 ms	1116 KB	Output is correct
6	Correct	0 ms	436 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	372 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	3 ms	1116 KB	Output is correct
11	Correct	2 ms	860 KB	Output is correct
12	Correct	4 ms	1372 KB	Output is correct
13	Correct	2 ms	1116 KB	Output is correct
14	Correct	3 ms	1116 KB	Output is correct
15	Correct	11 ms	3096 KB	Output is correct
16	Correct	11 ms	3152 KB	Output is correct
17	Correct	10 ms	2908 KB	Output is correct
18	Correct	7 ms	2316 KB	Output is correct

Subtask #2

70.0 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1116 KB	Output is correct
2	Correct	48 ms	16468 KB	Output is correct
3	Correct	372 ms	171856 KB	Output is correct
4	Correct	108 ms	40468 KB	Output is correct
5	Correct	209 ms	91192 KB	Output is correct
6	Correct	764 ms	198668 KB	Output is correct
7	Correct	3 ms	860 KB	Output is correct
8	Correct	2 ms	1116 KB	Output is correct
9	Correct	2 ms	1116 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	2 ms	1116 KB	Output is correct
12	Correct	1 ms	604 KB	Output is correct
13	Correct	55 ms	16476 KB	Output is correct
14	Correct	32 ms	10076 KB	Output is correct
15	Correct	26 ms	11132 KB	Output is correct
16	Correct	23 ms	6888 KB	Output is correct
17	Correct	144 ms	43716 KB	Output is correct
18	Correct	108 ms	43088 KB	Output is correct
19	Correct	111 ms	40528 KB	Output is correct
20	Correct	85 ms	37288 KB	Output is correct
21	Correct	214 ms	94288 KB	Output is correct
22	Correct	198 ms	91076 KB	Output is correct
23	Correct	287 ms	78160 KB	Output is correct
24	Correct	224 ms	92240 KB	Output is correct
25	Correct	451 ms	171544 KB	Output is correct
26	Correct	544 ms	222160 KB	Output is correct
27	Correct	689 ms	214856 KB	Output is correct
28	Correct	765 ms	198612 KB	Output is correct
29	Correct	746 ms	195096 KB	Output is correct
30	Correct	705 ms	201052 KB	Output is correct
31	Correct	481 ms	103756 KB	Output is correct
32	Correct	582 ms	197292 KB	Output is correct