Submission #1252494

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252494		tranvinhhuy2010	Obstacles for a Llama (IOI25_obstacles)	C++20	10 / 100	2094 ms	9028 KiB

obstacles

#include <vector>
using namespace std;

const int MAXM = 200005;
int parent[MAXM];

int find(int x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);
}
void unite(int x, int y) {
    parent[find(x)] = find(y);
}

vector<int> T_global, H_global;
vector<bool> free_cell; // free_cell[j] = T[0] > H[j]

void initialize(vector<int> T, vector<int> H) {
    T_global = T;
    H_global = H;
    int M = H.size();

    // mark which columns are free at row 0
    free_cell.assign(M, false);
    for (int j = 0; j < M; ++j) {
        if (T[0] > H[j]) {
            free_cell[j] = true;
        }
    }

    // initialize DSU
    for (int j = 0; j < M; ++j) parent[j] = j;

    // merge adjacent free columns in row 0
    for (int j = 0; j + 1 < M; ++j) {
        if (free_cell[j] && free_cell[j + 1]) {
            unite(j, j + 1);
        }
    }

    // check for vertical paths via other rows
    int N = T.size();
    for (int i = 1; i < N; ++i) {
        int t = T[i];
        int prev = -1;
        for (int j = 0; j < M; ++j) {
            if (t > H[j]) {
                if (free_cell[j]) {
                    if (prev != -1) unite(prev, j);
                    prev = j;
                }
            } else {
                prev = -1;
            }
        }
    }
}

bool can_reach(int L, int R, int S, int D) {
    if (find(S) != find(D)) return false;
    // check that all connectivity is within L to R
    if (S < L || S > R || D < L || D > R) return false;
    return true;
}

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