oj.uz

Submission #1082694

# Submission time Handle Problem Language Result Execution time Memory
1082694 2024-09-01T07:49:32 Z Grothendieck_505 Tracks in the Snow (BOI13_tracks) C++14
19.7917 / 100
 1396 ms 314068 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

int h, w;
vector<vector<char>> grid;
vector<vector<int>> component;
vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

// Function to perform BFS to mark all cells in the same component
void bfs(int x, int y, int comp_id) {
    queue<pair<int, int>> q;
    q.push({x, y});
    component[x][y] = comp_id;
    
    while (!q.empty()) {
        auto [cx, cy] = q.front();
        q.pop();
        
        for (auto [dx, dy] : directions) {
            int nx = cx + dx;
            int ny = cy + dy;
            
            if (nx >= 0 && nx < h && ny >= 0 && ny < w &&
                component[nx][ny] == -1 && grid[nx][ny] == grid[cx][cy]) {
                component[nx][ny] = comp_id;
                q.push({nx, ny});
            }
        }
    }
}

int solve() {
    component.assign(h, vector<int>(w, -1));
    int comp_id = 0;

    // Step 1: Identify all connected components of 'R' and 'F'
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (grid[i][j] != '.' && component[i][j] == -1) {
                bfs(i, j, comp_id++);
            }
        }
    }

    // Step 2: Build a graph between components (where edges exist between different track types)
    vector<vector<int>> adj(comp_id);
    vector<bool> visited(comp_id, false);

    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            for (auto [dx, dy] : directions) {
                int nx = i + dx;
                int ny = j + dy;

                if (nx >= 0 && nx < h && ny >= 0 && ny < w &&
                    component[i][j] != component[nx][ny] &&
                    grid[i][j] != grid[nx][ny]) {
                    adj[component[i][j]].push_back(component[nx][ny]);
                }
            }
        }
    }

    // Step 3: Perform BFS on the component graph to find the depth of the BFS tree
    queue<int> q;
    q.push(component[0][0]);
    visited[component[0][0]] = true;
    int depth = 0;

    while (!q.empty()) {
        int level_size = q.size();
        while (level_size--) {
            int curr = q.front();
            q.pop();

            for (int neighbor : adj[curr]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
        depth++;
    }

    return depth;
}

int main() {
    // Input reading
    cin >> h >> w;
    grid.resize(h, vector<char>(w));

    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> grid[i][j];
        }
    }

    // Solving the problem using the above approach
    int result = solve();

    // Output the result
    cout << result << endl;

    return 0;
}

Compilation message

tracks.cpp: In function 'void bfs(int, int, int)':
tracks.cpp:20:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |         auto [cx, cy] = q.front();
      |              ^
tracks.cpp:23:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |         for (auto [dx, dy] : directions) {
      |                   ^
tracks.cpp: In function 'int solve()':
tracks.cpp:55:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |             for (auto [dx, dy] : directions) {
      |                       ^

Subtask #1
6.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 4696 KB Execution killed with signal 11
2 Runtime error 1 ms 348 KB Execution killed with signal 11
3 Runtime error 1 ms 604 KB Execution killed with signal 11
4 Correct 11 ms 1884 KB Output is correct
5 Runtime error 5 ms 1628 KB Execution killed with signal 11
6 Runtime error 0 ms 348 KB Execution killed with signal 11
7 Runtime error 1 ms 348 KB Execution killed with signal 11
8 Correct 1 ms 348 KB Output is correct
9 Runtime error 1 ms 604 KB Execution killed with signal 11
10 Runtime error 5 ms 1628 KB Execution killed with signal 11
11 Correct 3 ms 684 KB Output is correct
12 Runtime error 8 ms 2072 KB Execution killed with signal 11
13 Runtime error 5 ms 1632 KB Execution killed with signal 11
14 Runtime error 4 ms 1884 KB Execution killed with signal 11
15 Runtime error 17 ms 4956 KB Execution killed with signal 11
16 Runtime error 19 ms 4700 KB Execution killed with signal 11
17 Runtime error 14 ms 4756 KB Execution killed with signal 11
18 Correct 13 ms 1768 KB Output is correct

Subtask #2
13.125 / 70.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1884 KB Execution killed with signal 11
2 Runtime error 84 ms 26940 KB Execution killed with signal 11
3 Runtime error 761 ms 244572 KB Execution killed with signal 11
4 Runtime error 180 ms 53588 KB Execution killed with signal 11
5 Runtime error 622 ms 313932 KB Execution killed with signal 11
6 Correct 1317 ms 160568 KB Output is correct
7 Runtime error 3 ms 1884 KB Execution killed with signal 11
8 Runtime error 4 ms 1884 KB Execution killed with signal 11
9 Runtime error 4 ms 1368 KB Execution killed with signal 11
10 Runtime error 2 ms 860 KB Execution killed with signal 11
11 Runtime error 3 ms 1628 KB Execution killed with signal 11
12 Runtime error 2 ms 1116 KB Execution killed with signal 11
13 Runtime error 89 ms 27072 KB Execution killed with signal 11
14 Runtime error 50 ms 15952 KB Execution killed with signal 11
15 Runtime error 56 ms 18312 KB Execution killed with signal 11
16 Runtime error 39 ms 11748 KB Execution killed with signal 11
17 Runtime error 232 ms 69460 KB Execution killed with signal 11
18 Runtime error 215 ms 70736 KB Execution killed with signal 11
19 Runtime error 175 ms 53548 KB Execution killed with signal 11
20 Runtime error 169 ms 53840 KB Execution killed with signal 11
21 Runtime error 449 ms 143696 KB Execution killed with signal 11
22 Runtime error 629 ms 314068 KB Execution killed with signal 11
23 Runtime error 432 ms 132136 KB Execution killed with signal 11
24 Runtime error 460 ms 171708 KB Execution killed with signal 11
25 Runtime error 896 ms 284600 KB Execution killed with signal 11
26 Correct 737 ms 72548 KB Output is correct
27 Correct 984 ms 98000 KB Output is correct
28 Correct 1396 ms 160552 KB Output is correct
29 Correct 1235 ms 146716 KB Output is correct
30 Correct 1169 ms 129456 KB Output is correct
31 Runtime error 835 ms 177840 KB Execution killed with signal 11
32 Runtime error 873 ms 181844 KB Execution killed with signal 11