Submission #1301065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301065		andria_gav	Obstacles for a Llama (IOI25_obstacles)	C++20	24 / 100	129 ms	11748 KiB

obstacles

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

int prnt[200005], sz[200005];
bool active[200005];
vector<pair<int,int>> cols;

int find_set(int v){
    return (prnt[v] == v ? v : prnt[v] = find_set(prnt[v]));
}

void union_set(int a, int b){
    a = find_set(a);
    b = find_set(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a,b);
    prnt[b] = a;
    sz[a] += sz[b];
}

vector<int> Tval, Hval;

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

    cols.clear();
    for (int i = 0; i < M; i++){
        prnt[i] = i;
        sz[i] = 1;
        active[i] = false;
        cols.push_back({H[i], i});
    }
    sort(cols.begin(), cols.end());

    int Tmax = *max_element(T.begin(), T.end());

    for (auto &p : cols){
        int h = p.first;
        int j = p.second;
        if (h >= Tmax) break;

        active[j] = true;
        if (j > 0 && active[j-1]) union_set(j, j-1);
        if (j+1 < M && active[j+1]) union_set(j, j+1);
    }
}

bool can_reach(int L, int R, int S, int D){
    return find_set(S) == find_set(D);
}

• 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