oj.uz

답안 #777794

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
777794 2023-07-09T16:12:52 Z overwatch9 Tracks in the Snow (BOI13_tracks) C++17
47.5 / 100
 2000 ms 47808 KB 
#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
vector <string> grid;
int n, m;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int bfs() {
    int covered = 1;
    queue <pair <int, int>> q;
    q.push({n-1, m-1});
    vector <vector <bool>> vis(n, vector <bool> (m));
    vis[n-1][m-1] = true;
    char og = grid[n-1][m-1];
    if (og == 'R')
        grid[n-1][m-1] = 'F';
    else
        grid[n-1][m-1] = 'R'; 
    while (!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m)
                continue;
            if (vis[nx][ny] || grid[nx][ny] != og)
                continue;
            covered++;
            if (og == 'R')
                grid[nx][ny] = 'F';
            else
                grid[nx][ny] = 'R';
            q.push({nx, ny});
        }
    }
    return covered;
}
int main() {
    cin >> n >> m;
    grid.resize(n);
    for (int i = 0; i < n; i++)
        cin >> grid[i];
    int ans = 1;
    int lst = bfs();
    while (true) {
        int res = bfs();
        ans++;
        if (res == lst)
            break;
        lst = res;
    }
    cout << ans-1 << '\n';
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 1012 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 16 ms 724 KB Output is correct
5 Correct 37 ms 468 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 47 ms 468 KB Output is correct
11 Correct 5 ms 360 KB Output is correct
12 Correct 46 ms 468 KB Output is correct
13 Correct 43 ms 540 KB Output is correct
14 Correct 37 ms 436 KB Output is correct
15 Correct 311 ms 980 KB Output is correct
16 Correct 127 ms 1064 KB Output is correct
17 Correct 242 ms 980 KB Output is correct
18 Correct 16 ms 724 KB Output is correct

Subtask #2
17.5 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1658 ms 728 KB Output is correct
2 Execution timed out 2062 ms 4436 KB Time limit exceeded
3 Execution timed out 2053 ms 47248 KB Time limit exceeded
4 Execution timed out 2067 ms 11656 KB Time limit exceeded
5 Execution timed out 2074 ms 21704 KB Time limit exceeded
6 Execution timed out 2041 ms 47268 KB Time limit exceeded
7 Correct 1458 ms 728 KB Output is correct
8 Correct 1659 ms 724 KB Output is correct
9 Correct 94 ms 468 KB Output is correct
10 Correct 316 ms 340 KB Output is correct
11 Correct 593 ms 728 KB Output is correct
12 Correct 1281 ms 352 KB Output is correct
13 Execution timed out 2055 ms 4404 KB Time limit exceeded
14 Execution timed out 2062 ms 3012 KB Time limit exceeded
15 Execution timed out 2071 ms 3284 KB Time limit exceeded
16 Execution timed out 2070 ms 1772 KB Time limit exceeded
17 Execution timed out 2073 ms 12484 KB Time limit exceeded
18 Execution timed out 2079 ms 12308 KB Time limit exceeded
19 Execution timed out 2084 ms 11652 KB Time limit exceeded
20 Execution timed out 2078 ms 10700 KB Time limit exceeded
21 Execution timed out 2058 ms 22388 KB Time limit exceeded
22 Execution timed out 2070 ms 21724 KB Time limit exceeded
23 Execution timed out 2057 ms 18436 KB Time limit exceeded
24 Execution timed out 2035 ms 22296 KB Time limit exceeded
25 Execution timed out 2057 ms 47600 KB Time limit exceeded
26 Correct 840 ms 27268 KB Output is correct
27 Execution timed out 2064 ms 47656 KB Time limit exceeded
28 Execution timed out 2048 ms 47564 KB Time limit exceeded
29 Execution timed out 2061 ms 47808 KB Time limit exceeded
30 Execution timed out 2081 ms 47024 KB Time limit exceeded
31 Execution timed out 2074 ms 23904 KB Time limit exceeded
32 Execution timed out 2071 ms 47712 KB Time limit exceeded