oj.uz

답안 #843151

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
843151 2023-09-03T18:11:16 Z Mizo_Compiler Tracks in the Snow (BOI13_tracks) C++17
97.8125 / 100
 699 ms 1048576 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 = 4002;
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) {
	fc[i][j] = true;
	vis[i][j] = true;
	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])dfs(nx, ny);
		} 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;
  	if (max(n, m) > 4000)while (1);
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 10076 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 8 ms 11228 KB Output is correct
5 Correct 2 ms 5724 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Correct 2 ms 5468 KB Output is correct
11 Correct 2 ms 7128 KB Output is correct
12 Correct 4 ms 7004 KB Output is correct
13 Correct 3 ms 5964 KB Output is correct
14 Correct 3 ms 5724 KB Output is correct
15 Correct 9 ms 9564 KB Output is correct
16 Correct 9 ms 10076 KB Output is correct
17 Correct 7 ms 9564 KB Output is correct
18 Correct 6 ms 11232 KB Output is correct

Subtask #2
67.8125 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 46684 KB Output is correct
2 Correct 35 ms 17632 KB Output is correct
3 Correct 229 ms 48080 KB Output is correct
4 Correct 60 ms 24904 KB Output is correct
5 Correct 173 ms 38624 KB Output is correct
6 Correct 489 ms 101980 KB Output is correct
7 Correct 13 ms 47704 KB Output is correct
8 Correct 10 ms 46684 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 10 ms 47316 KB Output is correct
12 Correct 1 ms 6748 KB Output is correct
13 Correct 35 ms 17632 KB Output is correct
14 Correct 25 ms 12888 KB Output is correct
15 Correct 17 ms 16128 KB Output is correct
16 Correct 16 ms 7004 KB Output is correct
17 Correct 86 ms 28100 KB Output is correct
18 Correct 66 ms 28228 KB Output is correct
19 Correct 57 ms 24920 KB Output is correct
20 Correct 55 ms 25324 KB Output is correct
21 Correct 135 ms 40920 KB Output is correct
22 Correct 164 ms 38740 KB Output is correct
23 Correct 163 ms 32728 KB Output is correct
24 Correct 142 ms 41044 KB Output is correct
25 Correct 259 ms 48188 KB Output is correct
26 Runtime error 699 ms 1048576 KB Execution killed with signal 9
27 Correct 609 ms 358204 KB Output is correct
28 Correct 494 ms 103212 KB Output is correct
29 Correct 486 ms 109612 KB Output is correct
30 Correct 474 ms 108752 KB Output is correct
31 Correct 330 ms 42764 KB Output is correct
32 Correct 380 ms 66368 KB Output is correct