oj.uz

답안 #843171

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
843171 2023-09-03T18:35:55 Z Mizo_Compiler Tracks in the Snow (BOI13_tracks) C++
97.8125 / 100
 690 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 = 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) {
	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]) {
              vis[nx][ny] = fc[nx][ny] = true;
              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;
	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 9 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 7 ms 11388 KB Output is correct
5 Correct 3 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 3 ms 5468 KB Output is correct
11 Correct 2 ms 7004 KB Output is correct
12 Correct 4 ms 7156 KB Output is correct
13 Correct 3 ms 5944 KB Output is correct
14 Correct 2 ms 5724 KB Output is correct
15 Correct 9 ms 9564 KB Output is correct
16 Correct 10 ms 10112 KB Output is correct
17 Correct 7 ms 9560 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 38 ms 19036 KB Output is correct
3 Correct 232 ms 48088 KB Output is correct
4 Correct 63 ms 24912 KB Output is correct
5 Correct 159 ms 38664 KB Output is correct
6 Correct 483 ms 101668 KB Output is correct
7 Correct 10 ms 47704 KB Output is correct
8 Correct 10 ms 46684 KB Output is correct
9 Correct 2 ms 5080 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 11 ms 47472 KB Output is correct
12 Correct 1 ms 6748 KB Output is correct
13 Correct 36 ms 19164 KB Output is correct
14 Correct 24 ms 13144 KB Output is correct
15 Correct 18 ms 15964 KB Output is correct
16 Correct 16 ms 7056 KB Output is correct
17 Correct 88 ms 28576 KB Output is correct
18 Correct 61 ms 26348 KB Output is correct
19 Correct 60 ms 24888 KB Output is correct
20 Correct 54 ms 25172 KB Output is correct
21 Correct 135 ms 41112 KB Output is correct
22 Correct 158 ms 38612 KB Output is correct
23 Correct 163 ms 32084 KB Output is correct
24 Correct 142 ms 41168 KB Output is correct
25 Correct 270 ms 47956 KB Output is correct
26 Runtime error 690 ms 1048576 KB Execution killed with signal 9
27 Correct 583 ms 358844 KB Output is correct
28 Correct 481 ms 102128 KB Output is correct
29 Correct 485 ms 110168 KB Output is correct
30 Correct 447 ms 111276 KB Output is correct
31 Correct 324 ms 42580 KB Output is correct
32 Correct 369 ms 66368 KB Output is correct