oj.uz

Submission #1099931

# Submission time Handle Problem Language Result Execution time Memory
1099931 2024-10-12T06:16:24 Z cozitsher Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1541 ms 494156 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define ff first
#define ss second
#define pb push_back

const int MAX_SIZE = 4444;  // Define maximum grid size
char meadow[MAX_SIZE][MAX_SIZE];  // Grid to hold the characters representing the meadow
bool visited[MAX_SIZE][MAX_SIZE];  // Visited array to track which cells have been processed
int dx[4] = {1, -1, 0, 0};  // Direction vectors for row movements (down, up)
int dy[4] = {0, 0, 1, -1};  // Direction vectors for column movements (right, left)

pair<int, int> parent[MAX_SIZE][MAX_SIZE];  // Array to store parent coordinates for each cell
int level[MAX_SIZE][MAX_SIZE];  // Array to store the level (or component ID) for each cell
bool levelVisited[MAX_SIZE * MAX_SIZE];  // Array to check if a level has been visited

signed main() {
    int n, m;  // Dimensions of the grid
    cin >> n >> m;  // Input the dimensions of the meadow

    // Input the characters into the meadow grid
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> meadow[i][j];
        }
    }

    queue<pair<int, int>> sameTypeQueue;  // Queue for cells of the same type
    queue<pair<int, int>> differentTypeQueue;  // Queue for cells of different types (tracks)

    // Start BFS from the bottom-right corner of the grid
    sameTypeQueue.push({n, m});
    int distinctLevels = 1;  // Initialize distinct animal count

    while (!(sameTypeQueue.empty() && differentTypeQueue.empty())) {
        int y, x;  // Current cell coordinates

        // Process cells from the same type queue
        if (!sameTypeQueue.empty()) {
            y = sameTypeQueue.front().ff;
            x = sameTypeQueue.front().ss;
            sameTypeQueue.pop();

            if (visited[y][x]) continue;  // Skip if already visited
        }
        // Process cells from the different type queue
        else {
            y = differentTypeQueue.front().ff;
            x = differentTypeQueue.front().ss;
            differentTypeQueue.pop();

            if (!visited[y][x]) {  // If cell is not visited
                int parentY = parent[y][x].ff;  // Get parent coordinates
                int parentX = parent[y][x].ss;

                // Check if the parent level is visited; if not, increment distinct animal count
                if (!levelVisited[level[parentY][parentX]]) {
                    distinctLevels++;
                }
                levelVisited[level[parentY][parentX]] = true;  // Mark this level as visited
            }
        }

        // Continue if out of bounds
        if (y < 1 || y > n || x < 1 || x > m) continue;

        visited[y][x] = true;  // Mark the current cell as visited
        level[y][x] = distinctLevels;  // Assign the current level to the cell

        // Explore neighboring cells
        for (int i = 0; i < 4; i++) {
            int newY = y + dy[i];  // New row coordinate
            int newX = x + dx[i];  // New column coordinate

            if (!visited[newY][newX]) {  // If the neighboring cell is not visited
                if (meadow[newY][newX] == meadow[y][x]) {  // Same type
                    sameTypeQueue.push({newY, newX});  // Add to same type queue
                }
                else if (meadow[newY][newX] == 'F' || meadow[newY][newX] == 'R') {  // Different type (tracks)
                    parent[newY][newX] = {y, x};  // Set parent of this cell
                    differentTypeQueue.push({newY, newX});  // Add to different type queue
                }
            }
        }
    }

    cout << distinctLevels;  // Output the count of distinct animals (connected components)
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 14672 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 14 ms 12892 KB Output is correct
5 Correct 5 ms 6640 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1372 KB Output is correct
9 Correct 1 ms 2140 KB Output is correct
10 Correct 5 ms 5212 KB Output is correct
11 Correct 4 ms 4736 KB Output is correct
12 Correct 10 ms 7516 KB Output is correct
13 Correct 6 ms 6748 KB Output is correct
14 Correct 6 ms 6748 KB Output is correct
15 Correct 23 ms 13464 KB Output is correct
16 Correct 26 ms 14684 KB Output is correct
17 Correct 19 ms 13916 KB Output is correct
18 Correct 14 ms 12976 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 57164 KB Output is correct
2 Correct 99 ms 39716 KB Output is correct
3 Correct 700 ms 188136 KB Output is correct
4 Correct 200 ms 116308 KB Output is correct
5 Correct 394 ms 172284 KB Output is correct
6 Correct 1541 ms 494156 KB Output is correct
7 Correct 27 ms 59472 KB Output is correct
8 Correct 25 ms 57088 KB Output is correct
9 Correct 4 ms 1628 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 35 ms 56480 KB Output is correct
12 Correct 4 ms 3672 KB Output is correct
13 Correct 108 ms 39648 KB Output is correct
14 Correct 63 ms 26448 KB Output is correct
15 Correct 60 ms 41248 KB Output is correct
16 Correct 48 ms 16336 KB Output is correct
17 Correct 260 ms 80136 KB Output is correct
18 Correct 218 ms 131664 KB Output is correct
19 Correct 179 ms 116332 KB Output is correct
20 Correct 153 ms 59988 KB Output is correct
21 Correct 409 ms 126288 KB Output is correct
22 Correct 444 ms 172276 KB Output is correct
23 Correct 507 ms 130644 KB Output is correct
24 Correct 434 ms 133144 KB Output is correct
25 Correct 830 ms 457668 KB Output is correct
26 Correct 717 ms 152856 KB Output is correct
27 Correct 1108 ms 382760 KB Output is correct
28 Correct 1489 ms 494112 KB Output is correct
29 Correct 1404 ms 493748 KB Output is correct
30 Correct 1249 ms 434772 KB Output is correct
31 Correct 1128 ms 306232 KB Output is correct
32 Correct 912 ms 302972 KB Output is correct