Submission #1256880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256880		christhegamechanger	Obstacles for a Llama (IOI25_obstacles)	C++17	0 / 100	2093 ms	2154412 KiB

obstacles

#include <vector>
#include <queue>
#include <cstring>

using namespace std;

static int N, M;
static vector<int> T, H;

void initialize(std::vector<int> t, std::vector<int> h) {
    N = t.size();
    M = h.size();
    T = t;
    H = h;
}

bool can_reach(int L, int R, int S, int D) {
    // If start and destination are the same
    if (S == D) return true;
    
    // BFS to find path from (0,S) to (0,D) within columns [L,R]
    int width = R - L + 1;
    vector<vector<bool>> visited(N, vector<bool>(width, false));
    queue<pair<int, int>> q;
    
    // Start from (0,S)
    // S-L is the column index in our restricted range
    q.push({0, S - L});
    visited[0][S - L] = true;
    
    while (!q.empty()) {
        int row = q.front().first;
        int col_idx = q.front().second;
        q.pop();
        
        // Convert back to actual column
        int actual_col = col_idx + L;
        
        // Check if we reached the destination
        if (row == 0 && actual_col == D) {
            return true;
        }
        
        // Try all 4 adjacent cells
        // Up
        if (row > 0) {
            if (!visited[row - 1][col_idx] && T[row - 1] > H[actual_col]) {
                visited[row - 1][col_idx] = true;
                q.push({row - 1, col_idx});
            }
        }
        
        // Down
        if (row < N - 1) {
            if (!visited[row + 1][col_idx] && T[row + 1] > H[actual_col]) {
                visited[row + 1][col_idx] = true;
                q.push({row + 1, col_idx});
            }
        }
        
        // Left
        if (col_idx > 0) {
            int new_actual_col = (col_idx - 1) + L;
            if (!visited[row][col_idx - 1] && T[row] > H[new_actual_col]) {
                visited[row][col_idx - 1] = true;
                q.push({row, col_idx - 1});
            }
        }
        
        // Right
        if (col_idx < width - 1) {
            int new_actual_col = (col_idx + 1) + L;
            if (!visited[row][col_idx + 1] && T[row] > H[new_actual_col]) {
                visited[row][col_idx + 1] = true;
                q.push({row, col_idx + 1});
            }
        }
    }
    
    return false;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 21
• Subtask 5: 0 / 25
• Subtask 6: 0 / 17