Submission #1256883

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

obstacles

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

using namespace std;

int N, M;
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;
    
    // Special case for N = 1
    if (N == 1) {
        // Just check connectivity in row 0
        int minCol = min(S, D);
        int maxCol = max(S, D);
        for (int j = minCol; j <= maxCol; j++) {
            if (T[0] <= H[j]) return false;
        }
        return true;
    }
    
    int width = R - L + 1;
    
    // Dynamic allocation for visited array
    vector<bool> visited(N * width, false);
    queue<int> q;
    
    // Helper function to convert (row, col) to index
    auto getIndex = [width, L](int row, int col) {
        return row * width + (col - L);
    };
    
    // Start from (0,S)
    int start_idx = getIndex(0, S);
    q.push(start_idx);
    visited[start_idx] = true;
    
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        
        int row = curr / width;
        int col = (curr % width) + L;
        
        // Check if we reached the destination
        if (row == 0 && col == D) {
            return true;
        }
        
        // Try all 4 directions
        const int dr[] = {-1, 1, 0, 0};
        const int dc[] = {0, 0, -1, 1};
        
        for (int dir = 0; dir < 4; dir++) {
            int new_row = row + dr[dir];
            int new_col = col + dc[dir];
            
            // Check bounds
            if (new_row < 0 || new_row >= N) continue;
            if (new_col < L || new_col > R) continue;
            
            // Check if cell is free of vegetation
            if (T[new_row] <= H[new_col]) continue;
            
            int new_idx = getIndex(new_row, new_col);
            
            // Check if already visited
            if (visited[new_idx]) continue;
            
            // Mark as visited and add to queue
            visited[new_idx] = true;
            q.push(new_idx);
        }
    }
    
    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