oj.uz

Submission #1082680

# Submission time Handle Problem Language Result Execution time Memory
1082680 2024-09-01T06:19:54 Z Grothendieck_505 Tracks in the Snow (BOI13_tracks) C++14
29.5833 / 100
 1051 ms 793092 KB 
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int h, w;
vector<vector<char>> grid;
vector<vector<bool>> visited;

// Directions for moving up, down, left, right
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

// Function to perform DFS to mark the connected components
void dfs(int x, int y, char animal) {
    visited[x][y] = true;
    for (int i = 0; i < 4; ++i) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < h && ny >= 0 && ny < w && !visited[nx][ny] && grid[nx][ny] == animal) {
            dfs(nx, ny, animal);
        }
    }
}

int main() {
    // Input reading
    cin >> h >> w;
    grid.resize(h, vector<char>(w));
    visited.resize(h, vector<bool>(w, false));
    
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> grid[i][j];
        }
    }
    
    int components = 0;

    // Iterate through all cells
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            // If the cell has not been visited and is either 'R' or 'F'
            if (!visited[i][j] && grid[i][j] != '.') {
                // Start a DFS for this component
                dfs(i, j, grid[i][j]);
                components++;
            }
        }
    }

    // Output the number of components
    cout << components << endl;

    return 0;
}

Subtask #1
3.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 860 KB Output isn't correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 8 ms 1372 KB Output isn't correct
5 Incorrect 3 ms 604 KB Output isn't correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Incorrect 1 ms 348 KB Output isn't correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Incorrect 3 ms 604 KB Output isn't correct
11 Incorrect 2 ms 860 KB Output isn't correct
12 Incorrect 6 ms 856 KB Output isn't correct
13 Incorrect 4 ms 604 KB Output isn't correct
14 Incorrect 4 ms 632 KB Output isn't correct
15 Incorrect 13 ms 1068 KB Output isn't correct
16 Incorrect 15 ms 860 KB Output isn't correct
17 Incorrect 12 ms 860 KB Output isn't correct
18 Incorrect 9 ms 1372 KB Output isn't correct

Subtask #2
26.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1116 KB Output is correct
2 Incorrect 64 ms 3912 KB Output isn't correct
3 Incorrect 596 ms 31252 KB Output isn't correct
4 Incorrect 125 ms 8016 KB Output isn't correct
5 Correct 348 ms 17832 KB Output is correct
6 Incorrect 832 ms 62032 KB Output isn't correct
7 Correct 3 ms 1112 KB Output is correct
8 Correct 3 ms 1116 KB Output is correct
9 Incorrect 3 ms 600 KB Output isn't correct
10 Correct 1 ms 604 KB Output is correct
11 Incorrect 2 ms 1116 KB Output isn't correct
12 Correct 1 ms 492 KB Output is correct
13 Incorrect 64 ms 3408 KB Output isn't correct
14 Incorrect 36 ms 2392 KB Output isn't correct
15 Correct 37 ms 2384 KB Output is correct
16 Incorrect 29 ms 1624 KB Output isn't correct
17 Incorrect 165 ms 7632 KB Output isn't correct
18 Correct 145 ms 7564 KB Output is correct
19 Incorrect 123 ms 7248 KB Output isn't correct
20 Incorrect 123 ms 6640 KB Output isn't correct
21 Incorrect 321 ms 16440 KB Output isn't correct
22 Correct 332 ms 15700 KB Output is correct
23 Incorrect 312 ms 13660 KB Output isn't correct
24 Correct 312 ms 15696 KB Output is correct
25 Correct 637 ms 27348 KB Output is correct
26 Correct 1051 ms 793092 KB Output is correct
27 Incorrect 829 ms 209996 KB Output isn't correct
28 Incorrect 831 ms 62292 KB Output isn't correct
29 Incorrect 799 ms 55888 KB Output isn't correct
30 Incorrect 839 ms 121684 KB Output isn't correct
31 Incorrect 631 ms 12768 KB Output isn't correct
32 Incorrect 836 ms 288748 KB Output isn't correct