oj.uz

Submission #362389

# Submission time Handle Problem Language Result Execution time Memory
362389 2021-02-02T21:09:26 Z __SIGSEGV__ Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 752 ms 128860 KB 
#include <bits/stdc++.h>
#define rep(x,a,b) for (int x = (int) (a); x < (int) (b); x++) 
#define REP(x,a) for (int x = 0; x < (int) (a); x++)
#define per(x,a,b) for (int x = (int) (a); x >= (int) (b); x--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define eb emplace_back
#define tcT template<class T
#define tcTU template<class T, class U

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const ll INF = (ll) 1e18;
const int X[]={1,0,-1,0}, Y[]={0, -1, 0, 1};
/*BITS*/
int csb(int x) { return __builtin_popcount(x); }
int ctz(int x) { return __builtin_ctz(x); }
bool isSet(int x, int pos) { return (x & (1 << pos)) != 0; }
tcT> bool cmin(T &a, T b) { return a > b ? (a = b, true) : false; }
tcT> bool cmax(T &a, T b) { return a < b ? (a = b, true) : false; }

int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cout.precision(10);
	cout << fixed;
	int h, w;
	cin >> h >> w;
	vector<string> grid(h);
	for (int i = 0; i < h; i++)
		cin >> grid[i];
	deque<pii> q;
	vector<vector<int>> dep(h, vector<int>(w, INT_MAX));
	vector<vector<bool>> vis(h, vector<bool>(w, false));
	q.push_front({0, 0});
	dep[0][0] = 1;
	vis[0][0] = true;
	int answer = 0;
	while (!q.empty()) {
		pii at = q.front();
		// cerr << at.first << " " << at.second << '\n';
		q.pop_front();
		for (int dir = 0; dir < 4; dir++) {
			int i = at.first + Y[dir];
			int j = at.second + X[dir];
			if (i >= 0 && i < h && j >= 0 && j < w && !vis[i][j]) {
				if (grid[i][j] == '.') continue;
				if (grid[i][j] == grid[at.first][at.second]) {
					cmin(dep[i][j], dep[at.first][at.second]);
					cmax(answer, dep[i][j]);
					q.push_front({i, j});
					vis[i][j] = true;
				} else {
					cmin(dep[i][j], dep[at.first][at.second] + 1);
					cmax(answer, dep[i][j]);
					q.push_back({i, j});
					vis[i][j] = true;
				}
			}
		}
	}		
	cout << answer << '\n';
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1900 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 7 ms 1516 KB Output is correct
5 Correct 2 ms 876 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 2 ms 748 KB Output is correct
11 Correct 2 ms 620 KB Output is correct
12 Correct 5 ms 876 KB Output is correct
13 Correct 3 ms 896 KB Output is correct
14 Correct 2 ms 876 KB Output is correct
15 Correct 11 ms 1900 KB Output is correct
16 Correct 12 ms 1900 KB Output is correct
17 Correct 8 ms 1900 KB Output is correct
18 Correct 7 ms 1516 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1132 KB Output is correct
2 Correct 44 ms 9964 KB Output is correct
3 Correct 242 ms 98796 KB Output is correct
4 Correct 67 ms 23404 KB Output is correct
5 Correct 170 ms 55532 KB Output is correct
6 Correct 752 ms 112096 KB Output is correct
7 Correct 2 ms 1260 KB Output is correct
8 Correct 2 ms 1132 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 2 ms 1132 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 43 ms 9964 KB Output is correct
14 Correct 24 ms 5996 KB Output is correct
15 Correct 17 ms 6508 KB Output is correct
16 Correct 21 ms 4332 KB Output is correct
17 Correct 117 ms 25196 KB Output is correct
18 Correct 71 ms 24940 KB Output is correct
19 Correct 67 ms 23404 KB Output is correct
20 Correct 56 ms 21484 KB Output is correct
21 Correct 144 ms 57452 KB Output is correct
22 Correct 169 ms 55532 KB Output is correct
23 Correct 228 ms 47852 KB Output is correct
24 Correct 146 ms 56044 KB Output is correct
25 Correct 455 ms 98668 KB Output is correct
26 Correct 625 ms 125660 KB Output is correct
27 Correct 710 ms 128860 KB Output is correct
28 Correct 751 ms 112224 KB Output is correct
29 Correct 745 ms 110444 KB Output is correct
30 Correct 737 ms 114804 KB Output is correct
31 Correct 576 ms 63596 KB Output is correct
32 Correct 668 ms 119928 KB Output is correct