oj.uz

Submission #843168

# Submission time Handle Problem Language Result Execution time Memory
843168 2023-09-03T18:33:46 Z Mizo_Compiler Tracks in the Snow (BOI13_tracks) C++
100 / 100
 488 ms 74984 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
#define pb push_back
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
const int N = 4000;
int n, m, ans = 1;
char c[N][N];
bool fc[N][N];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
vector<pair<int, int>> f, r;
bool vis[N][N];

void dfs(int i, int j) {
	queue<pair<int, int>> q;
  	q.push({i, j});
  	while (!q.empty()) {
      i = q.front().F, j = q.front().S;
      q.pop();
      for (int ii = 0; ii < 4; ii++) {
		int nx = i + dx[ii], ny = j + dy[ii];
		if (nx < 0 || ny < 0 || nx >= n || ny >= m)continue;
		if (c[nx][ny] == c[0][0]) {
			if (!fc[nx][ny]) {
              q.push({nx, ny});
              vis[nx][ny] = fc[nx][ny] = true;
            }
		} else if (!vis[nx][ny]) {
			if (c[nx][ny] == 'F')f.pb({nx, ny});
			else if (c[nx][ny] == 'R')r.pb({nx, ny});
			vis[nx][ny] = true;
		}
	}
    }
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> c[i][j];
		}
	}
	dfs(0, 0);
	char cur = 'R';
	if (c[0][0] == cur)cur = 'F';
	while (!f.empty() || !r.empty()) {
		if (cur == 'R') {
			if (!r.empty())ans++;
			while (!r.empty()) {
				int x = r.back().F, y = r.back().S;
				r.pop_back();
				for (int i = 0; i < 4; i++) {
					int nx = x + dx[i], ny = y + dy[i];
					if (nx < 0 || ny < 0 || nx >= n || ny >= m)continue;
					if (vis[nx][ny])continue;
					vis[nx][ny] = true;
					if (c[nx][ny] == 'R')r.pb({nx, ny});
					else if (c[nx][ny] == 'F')f.pb({nx, ny});
				}
			}
		} else {
			if (!f.empty()) {
				ans++;
			}
			while (!f.empty()) {
				int x = f.back().F, y = f.back().S;
				f.pop_back();
				for (int i = 0; i < 4; i++) {
					int nx = x + dx[i], ny = y + dy[i];
					if (nx < 0 || ny < 0 || nx >= n || ny >= m)continue;
					if (vis[nx][ny])continue;
					vis[nx][ny] = true;
					if (c[nx][ny] == 'R')r.pb({nx, ny});
					else if (c[nx][ny] == 'F')f.pb({nx, ny});
				}
			}
		}
		if (cur == 'F')cur = 'R';
		else cur = 'F';
	}
	cout << ans;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 9820 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 6 ms 10208 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 6748 KB Output is correct
8 Correct 1 ms 6744 KB Output is correct
9 Correct 1 ms 4956 KB Output is correct
10 Correct 3 ms 5468 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 4 ms 5980 KB Output is correct
13 Correct 2 ms 6872 KB Output is correct
14 Correct 3 ms 6748 KB Output is correct
15 Correct 9 ms 9564 KB Output is correct
16 Correct 9 ms 9816 KB Output is correct
17 Correct 7 ms 9308 KB Output is correct
18 Correct 6 ms 10200 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 46172 KB Output is correct
2 Correct 38 ms 17564 KB Output is correct
3 Correct 231 ms 47316 KB Output is correct
4 Correct 56 ms 24536 KB Output is correct
5 Correct 159 ms 37976 KB Output is correct
6 Correct 471 ms 73076 KB Output is correct
7 Correct 10 ms 47196 KB Output is correct
8 Correct 11 ms 46172 KB Output is correct
9 Correct 2 ms 4444 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 10 ms 46940 KB Output is correct
12 Correct 2 ms 6748 KB Output is correct
13 Correct 33 ms 17540 KB Output is correct
14 Correct 21 ms 13580 KB Output is correct
15 Correct 18 ms 15708 KB Output is correct
16 Correct 15 ms 7480 KB Output is correct
17 Correct 88 ms 27472 KB Output is correct
18 Correct 59 ms 25936 KB Output is correct
19 Correct 60 ms 24548 KB Output is correct
20 Correct 53 ms 24800 KB Output is correct
21 Correct 133 ms 40396 KB Output is correct
22 Correct 157 ms 37968 KB Output is correct
23 Correct 161 ms 32080 KB Output is correct
24 Correct 139 ms 40412 KB Output is correct
25 Correct 273 ms 47524 KB Output is correct
26 Correct 374 ms 44112 KB Output is correct
27 Correct 488 ms 53256 KB Output is correct
28 Correct 479 ms 71732 KB Output is correct
29 Correct 458 ms 66084 KB Output is correct
30 Correct 447 ms 74984 KB Output is correct
31 Correct 331 ms 41936 KB Output is correct
32 Correct 367 ms 65212 KB Output is correct