Submission #1251589

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251589		fv3	Obstacles for a Llama (IOI25_obstacles)	C++20	0 / 100	59 ms	9796 KiB

obstacles

#include "obstacles.h"
#include <bits/stdc++.h>

using namespace std;
#define all(x) x.begin(), x.end()

struct union_find {
    vector<int> sz, lft;

    union_find(int n) {
        sz = lft = vector<int>(n, 1);
        iota(all(lft), 0);
    }

    int find(int i) {
        if (lft[i] == i) return i;
        return lft[i] = find(lft[i]);
    }

    void merge(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return;

        if (sz[a] < sz[b]) {
            swap(a, b);
        }
        lft[b] = a;
        sz[a] += sz[b];
    }
} dsu(0);

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

    assert(N <= 3);
    dsu = union_find(N * M);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (T[i] <= H[j]) continue;
            if (j < M - 1 && T[i] > H[j + 1]) {
                dsu.merge(i * M + j, i * M + j + 1);
            }
            if (i < N - 1 && T[i+1] > H[j]) {
                dsu.merge(i * M + j, i * M + j + M);
            }
        }
    }
}

bool can_reach(int L, int R, int S, int D) {
    return dsu.find(R) == dsu.find(S);
}

//#include "grader.cpp"

• 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