oj.uz

답안 #867583

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
867583 2023-10-28T20:02:03 Z saarang123 Tracks in the Snow (BOI13_tracks) C++17
45.1042 / 100
 2000 ms 195168 KB 
#include <bits/stdc++.h>
using namespace std;

int n, m;
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

bool check(int nx, int ny){
	return (nx >= 0 && nx < n && ny >= 0 && ny < m);
}

struct item{
	int x, y, dist;
};

struct comp{
	bool operator()(item a, item b){
		return (a.dist < b.dist) || (a.dist == b.dist && make_pair(a.x, a.y) < make_pair(b.x, b.y));
	}
};

int bfs(vector<vector<char>>& grid){
	priority_queue<item, vector<item>, comp> q;
	q.push({0, 0, 1});
	vector<vector<int>> dist(n, vector<int>(m, 1e9));
	dist[0][0] = 1;
	while (!q.empty()){
		item i = q.top(); q.pop();
		if (dist[i.x][i.y] != i.dist) continue;
		for (int j = 0; j < 4; j++){
			int nx = i.x + dx[j], ny = i.y + dy[j];
			if (!check(nx, ny)) continue;
			if (grid[nx][ny] == '.') continue;
			int ndist = i.dist + (grid[nx][ny] != grid[i.x][i.y]);
			if (ndist < dist[nx][ny]){
				dist[nx][ny] = ndist;
				q.push({nx, ny, ndist});
			}
		}
	}

	//max distance
	int mx = 0;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			//cout << (dist[i][j] == 1e9 ? 0 : dist[i][j]) << ' ';
			if (grid[i][j] == '.') continue;
			if (dist[i][j] > mx){
				mx = dist[i][j];
			}
		}
		//cout << '\n';
	}
	return mx;
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	vector<vector<char>> grid(n, vector<char>(m));
	vector<int> cnt(2, 0); //r, f
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			cin >> grid[i][j];
			if (grid[i][j] == 'F') cnt[1]++;
			if (grid[i][j] == 'R') cnt[0]++;
		}
	}

	//empty
	if (grid[0][0] == '.'){
		cout << "0\n";
		return 0;
	}
	
	//ans
	cout << bfs(grid) << '\n';
}

Subtask #1
16.6666666667 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2093 ms 3536 KB Time limit exceeded
2 Correct 0 ms 344 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Execution timed out 2091 ms 2952 KB Time limit exceeded
5 Correct 1653 ms 1032 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 127 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 1449 ms 912 KB Output is correct
11 Execution timed out 2035 ms 1048 KB Time limit exceeded
12 Execution timed out 2067 ms 1372 KB Time limit exceeded
13 Correct 1644 ms 1024 KB Output is correct
14 Correct 1637 ms 1032 KB Output is correct
15 Execution timed out 2035 ms 2040 KB Time limit exceeded
16 Execution timed out 2061 ms 3532 KB Time limit exceeded
17 Execution timed out 2067 ms 2360 KB Time limit exceeded
18 Execution timed out 2013 ms 3028 KB Time limit exceeded

Subtask #2
28.4375 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 856 KB Output is correct
2 Execution timed out 2079 ms 10452 KB Time limit exceeded
3 Execution timed out 2095 ms 95580 KB Time limit exceeded
4 Execution timed out 2060 ms 22612 KB Time limit exceeded
5 Correct 211 ms 53584 KB Output is correct
6 Execution timed out 2072 ms 194172 KB Time limit exceeded
7 Correct 2 ms 856 KB Output is correct
8 Correct 2 ms 856 KB Output is correct
9 Execution timed out 2041 ms 860 KB Time limit exceeded
10 Correct 1 ms 604 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Execution timed out 2091 ms 10536 KB Time limit exceeded
14 Execution timed out 2045 ms 6188 KB Time limit exceeded
15 Correct 24 ms 6236 KB Output is correct
16 Execution timed out 2031 ms 4804 KB Time limit exceeded
17 Execution timed out 2012 ms 25084 KB Time limit exceeded
18 Correct 108 ms 24088 KB Output is correct
19 Execution timed out 2028 ms 22868 KB Time limit exceeded
20 Execution timed out 2024 ms 21608 KB Time limit exceeded
21 Execution timed out 2096 ms 56308 KB Time limit exceeded
22 Correct 212 ms 53468 KB Output is correct
23 Execution timed out 2085 ms 46512 KB Time limit exceeded
24 Correct 196 ms 54032 KB Output is correct
25 Correct 561 ms 94704 KB Output is correct
26 Correct 1487 ms 72976 KB Output is correct
27 Execution timed out 2013 ms 194420 KB Time limit exceeded
28 Execution timed out 2066 ms 193452 KB Time limit exceeded
29 Execution timed out 2008 ms 195168 KB Time limit exceeded
30 Execution timed out 2054 ms 93504 KB Time limit exceeded
31 Execution timed out 2041 ms 111496 KB Time limit exceeded
32 Execution timed out 2040 ms 145300 KB Time limit exceeded