Submission #1269326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269326		sula2	Obstacles for a Llama (IOI25_obstacles)	C++20	23 / 100	1115 ms	2162688 KiB

obstacles

#include <bits/stdc++.h>
using namespace std;

vector<int> T,H;
vector<vector<int>> comp;
int n,m;
pair<int,int> dir[] = {
        {0, 1},
        {1, 0},
        {0, -1},
        {-1, 0}
};

bool valid(int i, int j) {
    return 0 <= min(i, j) && i < n && j < m && T[i] > H[j] && comp[i][j] == 0;
}

void dfs(int i, int j, int c) {
    comp[i][j] = c;
    for (auto [di, dj] : dir) if (valid(i + di, j + dj))
        dfs(i + di, j + dj, c);
}

void initialize(vector<int> _T, vector<int> _H) {
    n = _T.size();
    m = _H.size();
    comp.resize(n, vector<int>(m));
    T = _T, H = _H;
    int c = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (valid(i, j))
                dfs(i, j, ++c);
}

bool can_reach(int l, int r, int s, int t) {
    return comp[0][s] == comp[0][t];
}

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