Submission #1251609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251609		fv3	Obstacles for a Llama (IOI25_obstacles)	C++20	24 / 100	79 ms	8264 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());

    dsu = union_find(M);

    for (int j = 0; j < M; j++) {
        if (T.back() <= H[j]) continue;

        if (j + 1 < M && T.back() > H[j + 1]) {
            dsu.merge(j, j + 1);
        }
    }
}

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

//#include "grader.cpp"

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