Submission #1099931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099931		cozitsher	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1541 ms	494156 KiB

tracks

#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 / 30
• Subtask 2: 70 / 70