oj.uz

답안 #499005

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
499005 2021-12-27T02:58:07 Z vbee Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 761 ms 238576 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define ii pair<int,int>
#define vii vector<ii>
#define vi vector<int>
#define fi first
#define se second
#define TASK ""
#define ll long long
#define pll pair<ll, ll>
#define vll vector<ll>
#define vpll vector<pll>
#define pb push_back
#define MASK(i) (1 << (i))
#define BIT(x, i) ((x >> (i)) & 1)
 
using namespace std;

const int oo = 1e9 + 7;
const ll loo = (ll)1e18 + 7;
const int N = 4e3 + 7; 
ll n, m, dist[N][N];
char a[N][N];
bool visited[N][N];
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
bool check(ll i, ll j){
	if (i < 1 || j < 1 || i > n || j > m || a[i][j] == '.' || visited[i][j]) return false;
	return true;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	//freopen(TASK".in", "r", stdin);
	//freopen(TASK".out", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			cin >> a[i][j];
		}
	}
	deque<pll> kew;
	kew.push_back({1, 1});
	visited[1][1] = true;
	ll res = 0;
	while (!kew.empty()){
		auto k = kew.front();
		kew.pop_front();
		res = max(res, dist[k.fi][k.se]);
		for (int i = 0; i < 4; i++){
			ll newx = k.fi + dx[i];
			ll newy = k.se + dy[i];
			if (check(newx, newy)){
				visited[newx][newy] = true;
				dist[newx][newy] = dist[k.fi][k.se];
				if (a[k.fi][k.se] == a[newx][newy]){
					kew.push_front({newx, newy});
				}
				else {
					dist[newx][newy]++;
					kew.push_back({newx, newy});
				}
			}
		}
	}
	cout << res + 1;
	return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 8252 KB Output is correct
2 Correct 1 ms 432 KB Output is correct
3 Correct 1 ms 832 KB Output is correct
4 Correct 10 ms 7880 KB Output is correct
5 Correct 4 ms 4304 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 1 ms 1100 KB Output is correct
9 Correct 1 ms 1472 KB Output is correct
10 Correct 5 ms 3528 KB Output is correct
11 Correct 3 ms 3136 KB Output is correct
12 Correct 7 ms 4556 KB Output is correct
13 Correct 6 ms 4300 KB Output is correct
14 Correct 4 ms 4288 KB Output is correct
15 Correct 13 ms 7920 KB Output is correct
16 Correct 15 ms 8344 KB Output is correct
17 Correct 11 ms 8008 KB Output is correct
18 Correct 9 ms 7884 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 46024 KB Output is correct
2 Correct 56 ms 22280 KB Output is correct
3 Correct 334 ms 91852 KB Output is correct
4 Correct 105 ms 50920 KB Output is correct
5 Correct 264 ms 74860 KB Output is correct
6 Correct 761 ms 184000 KB Output is correct
7 Correct 32 ms 48024 KB Output is correct
8 Correct 22 ms 46004 KB Output is correct
9 Correct 2 ms 844 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 22 ms 47180 KB Output is correct
12 Correct 2 ms 2252 KB Output is correct
13 Correct 57 ms 22316 KB Output is correct
14 Correct 47 ms 15904 KB Output is correct
15 Correct 35 ms 20676 KB Output is correct
16 Correct 24 ms 8772 KB Output is correct
17 Correct 133 ms 41092 KB Output is correct
18 Correct 117 ms 55936 KB Output is correct
19 Correct 101 ms 50928 KB Output is correct
20 Correct 80 ms 34600 KB Output is correct
21 Correct 197 ms 66768 KB Output is correct
22 Correct 236 ms 74816 KB Output is correct
23 Correct 247 ms 60356 KB Output is correct
24 Correct 216 ms 65740 KB Output is correct
25 Correct 558 ms 157892 KB Output is correct
26 Correct 505 ms 238576 KB Output is correct
27 Correct 652 ms 192936 KB Output is correct
28 Correct 759 ms 184232 KB Output is correct
29 Correct 753 ms 184736 KB Output is correct
30 Correct 688 ms 183940 KB Output is correct
31 Correct 607 ms 120020 KB Output is correct
32 Correct 588 ms 181944 KB Output is correct