Submission #1256264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256264		nibert	Obstacles for a Llama (IOI25_obstacles)	C++20	10 / 100	65 ms	17480 KiB

obstacles

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

struct DSU {
    vector<int> p, sz;
    DSU(int n): p(n), sz(n,1) { iota(p.begin(), p.end(), 0); }
    int find(int x){ return p[x]==x?x:p[x]=find(p[x]); }
    void unite(int a,int b){
        a=find(a); b=find(b);
        if(a==b) return;
        if(sz[a]<sz[b]) swap(a,b);
        p[b]=a; sz[a]+=sz[b];
    }
};

int N,M;
vector<int> T,H;
vector<int> linkRight; // linkRight[c] = furthest column reachable from col c in row 0
vector<int> maxReach;  // prefix max of linkRight

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

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

    // Step 1: mark free cells
    vector<char> freecell((long long)N * M, 0);
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(T[i] > H[j]) freecell[id(i,j)] = 1;
        }
    }

    // Step 2: build DSU for all free cells
    DSU dsu(N*M);
    // vertical edges
    for(int i=0;i<N-1;i++){
        for(int j=0;j<M;j++){
            if(freecell[id(i,j)] && freecell[id(i+1,j)])
                dsu.unite(id(i,j), id(i+1,j));
        }
    }
    // horizontal edges
    for(int i=0;i<N;i++){
        for(int j=0;j<M-1;j++){
            if(freecell[id(i,j)] && freecell[id(i,j+1)])
                dsu.unite(id(i,j), id(i,j+1));
        }
    }

    // Step 3: For each component touching row 0, find min & max column in row 0
    vector<int> minCol(N*M, M), maxCol(N*M, -1);
    for(int j=0;j<M;j++){
        if(freecell[id(0,j)]){
            int root = dsu.find(id(0,j));
            minCol[root] = min(minCol[root], j);
            maxCol[root] = max(maxCol[root], j);
        }
    }

    // Step 4: Build linkRight for each col in row 0
    linkRight.assign(M, -1);
    for(int j=0;j<M;j++){
        if(freecell[id(0,j)]){
            int root = dsu.find(id(0,j));
            linkRight[j] = maxCol[root];
        } else {
            linkRight[j] = j; // blocked cell: can only "reach" itself
        }
    }

    // Step 5: Build prefix maxReach
    maxReach.assign(M, -1);
    int curMax = -1;
    for(int j=0;j<M;j++){
        curMax = max(curMax, linkRight[j]);
        maxReach[j] = curMax;
    }
}

bool can_reach(int L, int R, int S, int D) {
    if(S > D) swap(S,D);
    // Check both start & end are free
    if(maxReach[S] < S || maxReach[D] < D) return false; // blocked cells
    // Check if reachable without leaving [L,R]
    if(S < L || D > R) return false;
    // The precomputed maxReach must cover D within [L,R]
    return maxReach[S] >= D;
}

• 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