Submission #1256263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256263		nibert	Obstacles for a Llama (IOI25_obstacles)	C++20	Compilation error	0 ms	0 KiB

obstacles

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

struct RollbackDSU {
    vector<int> p, sz;
    vector<pair<int,int>> stk;
    RollbackDSU(int n) : p(n), sz(n,1) { iota(p.begin(), p.end(), 0); }
    int find(int x) { while (x != p[x]) x = p[x]; return x; }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a,b);
        stk.push_back({b, sz[a]});
        p[b] = a; sz[a] += sz[b];
        return true;
    }
    int snapshot() { return (int)stk.size(); }
    void rollback(int t) {
        while ((int)stk.size() > t) {
            auto [b, sa] = stk.back(); stk.pop_back();
            int a = p[b];
            p[b] = b; sz[a] = sa;
        }
    }
};

inline int cell_id(int i, int j, int M) { return i*M + j; }

struct Query {
    int L, R, S, D, idx;
};

int N, M, Q;
vector<int> T, H;
vector<vector<int>> free_rows; // free_rows[j] = rows free in column j

void initialize(vector<int> t, vector<int> h) {
    T = t; H = h;
    N = T.size(); M = H.size();
    free_rows.assign(M, {});
    for (int j = 0; j < M; j++) {
        for (int i = 0; i < N; i++) {
            if (T[i] > H[j]) free_rows[j].push_back(i);
        }
    }
}

vector<int> process_queries(vector<Query> &queries) {
    int B = max(1, (int)(sqrt(M)));
    sort(queries.begin(), queries.end(), [&](const Query &a, const Query &b) {
        int blA = a.L / B, blB = b.L / B;
        if (blA != blB) return blA < blB;
        return a.R < b.R;
    });

    RollbackDSU dsu(N*M);
    vector<int> ans(Q, 0);
    vector<int> col_snapshot(M, -1);
    vector<bool> active(M, false);

    int curL = 0, curR = -1;

    auto add_col = [&](int c) {
        int snap = dsu.snapshot();
        // Vertical edges
        auto &rows = free_rows[c];
        for (int k = 0; k+1 < (int)rows.size(); k++) {
            if (rows[k+1] == rows[k]+1) {
                dsu.unite(cell_id(rows[k], c, M), cell_id(rows[k+1], c, M));
            }
        }
        // Horizontal edges
        if (c > 0 && active[c-1]) {
            auto &left = free_rows[c-1];
            auto &cur  = free_rows[c];
            // intersect sorted lists
            int p1=0, p2=0;
            while (p1<(int)left.size() && p2<(int)cur.size()) {
                if (left[p1] == cur[p2]) {
                    dsu.unite(cell_id(left[p1], c-1, M), cell_id(cur[p2], c, M));
                    p1++; p2++;
                } else if (left[p1] < cur[p2]) p1++;
                else p2++;
            }
        }
        if (c+1 < M && active[c+1]) {
            auto &right = free_rows[c+1];
            auto &cur   = free_rows[c];
            int p1=0, p2=0;
            while (p1<(int)right.size() && p2<(int)cur.size()) {
                if (right[p1] == cur[p2]) {
                    dsu.unite(cell_id(right[p1], c+1, M), cell_id(cur[p2], c, M));
                    p1++; p2++;
                } else if (right[p1] < cur[p2]) p1++;
                else p2++;
            }
        }
        active[c] = true;
        col_snapshot[c] = snap;
    };

    auto remove_col = [&](int c) {
        dsu.rollback(col_snapshot[c]);
        active[c] = false;
    };

    for (auto &qu : queries) {
        while (curR < qu.R) add_col(++curR);
        while (curR > qu.R) remove_col(curR--);
        while (curL < qu.L) remove_col(curL++);
        while (curL > qu.L) add_col(--curL);

        int idS = cell_id(0, qu.S, M);
        int idD = cell_id(0, qu.D, M);
        ans[qu.idx] = (dsu.find(idS) == dsu.find(idD));
    }
    return ans;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccOzQmsI.o: in function `main':
grader.cpp:(.text.startup+0x402): undefined reference to `can_reach(int, int, int, int)'
collect2: error: ld returned 1 exit status